Automata, Languages And Programming: 36th International Colloquium, Icalp 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I (lecture Notes In Computer Science)

The two-volume set LNCS 5555 and LNCS 5556 constitutes the refereed proceedings of the 36th International Colloquium on Automata, Languages and Programming, ICALP 2009, held in Rhodes, Greece, in July 2009. The 126 revised full papers (62 papers for track A, 24 for track B, and 22 for track C) presented were carefully reviewed and selected from a total of 370 submissions. The papers are grouped in three major tracks on algorithms, automata, complexity and games; on logic, semantics, theory of programming; as well as on foundations of networked computation: models, algorithms and information management. LNCS 5555 contains 62 contributions of track A selected from 223 submissions as well as 2 invited lectures. This two-volume set lauches the new subline of Lecture Notes in Computer Science, entitled LNCS Advanced Research in Computing and Software Science (ARCoSS). Front Matter....Pages - Assigning Papers to Referees....Pages 1-2 Algorithmic Game Theory: A Snapshot....Pages 3-11 SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs....Pages 12-23 Correlation Clustering Revisited: The “True” Cost of Error Minimization Problems....Pages 24-36 Sorting and Selection with Imprecise Comparisons....Pages 37-48 Fast FAST ....Pages 49-58 Bounds on the Size of Small Depth Circuits for Approximating Majority....Pages 59-70 Counting Subgraphs via Homomorphisms....Pages 71-82 External Sampling....Pages 83-94 Functional Monitoring without Monotonicity....Pages 95-106 De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results....Pages 107-118 Towards a Study of Low-Complexity Graphs....Pages 119-131 Decidability of Conjugacy of Tree-Shifts of Finite Type....Pages 132-143 Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule....Pages 144-155 Competitive Analysis of Aggregate Max in Windowed Streaming....Pages 156-170 Faster Regular Expression Matching....Pages 171-182 A Fast and Simple Parallel Algorithm for the Monotone Duality Problem....Pages 183-194 Unconditional Lower Bounds against Advice....Pages 195-209 Approximating Decision Trees with Multiway Branches....Pages 210-221 Annotations in Data Streams....Pages 222-234 The Tile Complexity of Linear Assemblies....Pages 235-253 A Graph Reduction Step Preserving Element-Connectivity and Applications....Pages 254-265 Approximating Matches Made in Heaven....Pages 266-278 Strong and Pareto Price of Anarchy in Congestion Games....Pages 279-291 A Better Algorithm for Random k -SAT....Pages 292-303 Exact and Approximate Bandwidth....Pages 304-315 Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs....Pages 316-327 Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs....Pages 328-340 On Cartesian Trees and Range Minimum Queries....Pages 341-353 Applications of a Splitting Trick....Pages 354-365 Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness....Pages 366-377 Incompressibility through Colors and IDs....Pages 378-389 Partition Arguments in Multiparty Communication Complexity....Pages 390-402 High Complexity Tilings with Sparse Errors....Pages 403-414 Tight Bounds for the Cover Time of Multiple Random Walks....Pages 415-426 Online Computation with Advice....Pages 427-438 Dynamic Succinct Ordered Trees....Pages 439-450 Universal Succinct Representations of Trees?....Pages 451-462 Distortion Is Fixed Parameter Tractable....Pages 463-474 Towards Optimal Range Medians....Pages 475-486 B-Treaps: A Uniquely Represented Alternative to B-Trees....Pages 487-499 Testing Fourier Dimensionality and Sparsity....Pages 500-512 Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams....Pages 513-524 Wireless Communication Is in APX....Pages 525-536 The Ehrenfeucht-Silberger Problem....Pages 537-548 Applications of Effective Probability Theory to Martin-Löf Randomness....Pages 549-561 An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables....Pages 562-573 Popular Mixed Matchings....Pages 574-584 Factoring Groups Efficiently....Pages 585-596 On Finding Dense Subgraphs....Pages 597-608 Learning Halfspaces with Malicious Noise....Pages 609-621 General Scheme for Perfect Quantum Network Coding with Free Classical Communication....Pages 622-633 Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost....Pages 634-652 Limits and Applications of Group Algebras for Parameterized Problems....Pages 653-664 Sleep with Guilt and Work Faster to Minimize Flow Plus Energy....Pages 665-676 Improved Bounds for Flow Shop Scheduling....Pages 677-688 A 3/2-Approximation Algorithm for General Stable Marriage....Pages 689-700 Limiting Negations in Formulas....Pages 701-712 Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems....Pages 713-725 Superhighness and Strong Jump Traceability....Pages 726-737 Amortized Communication Complexity of Distributions....Pages 738-749 The Number of Symbol Comparisons in QuickSort and QuickSelect....Pages 750-763 Computing the Girth of a Planar Graph in O ( n log n ) Time....Pages 764-773 Elimination Graphs....Pages 774-785 Back Matter....Pages -