Albers / Marchetti-Spaccamela / Matias Automata, Languages and Programming

36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I
2009
ISBN: 978-3-642-02927-1
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 789 Seiten, eBook

Reihe: Theoretical Computer Science and General Issues

Zielgruppe

Research

Autoren/Hrsg.

Albers, Susanne

Marchetti-Spaccamela, Alberto

Matias, Yossi

Nikoletseas, Sotiris

Thomas, Wolfgang

Inhaltsverzeichnis

Invited Lectures.- Assigning Papers to Referees.- Algorithmic Game Theory: A Snapshot.- Contributed Papers.- SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs.- Correlation Clustering Revisited: The “True” Cost of Error Minimization Problems.- Sorting and Selection with Imprecise Comparisons.- Fast FAST.- Bounds on the Size of Small Depth Circuits for Approximating Majority.- Counting Subgraphs via Homomorphisms.- External Sampling.- Functional Monitoring without Monotonicity.- De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results.- Towards a Study of Low-Complexity Graphs.- Decidability of Conjugacy of Tree-Shifts of Finite Type.- Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule.- Competitive Analysis of Aggregate Max in Windowed Streaming.- Faster Regular Expression Matching.- A Fast and Simple Parallel Algorithm for the Monotone Duality Problem.- Unconditional Lower Bounds against Advice.- Approximating Decision Trees with Multiway Branches.- Annotations in Data Streams.- The Tile Complexity of Linear Assemblies.- A Graph Reduction Step Preserving Element-Connectivity and Applications.- Approximating Matches Made in Heaven.- Strong and Pareto Price of Anarchy in Congestion Games.- A Better Algorithm for Random k-SAT.- Exact and Approximate Bandwidth.- Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs.- Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs.- On Cartesian Trees and Range Minimum Queries.- Applications of a Splitting Trick.- Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness.- Incompressibility through Colors and IDs.- Partition Arguments in Multiparty Communication Complexity.- High Complexity Tilings with SparseErrors.- Tight Bounds for the Cover Time of Multiple Random Walks.- Online Computation with Advice.- Dynamic Succinct Ordered Trees.- Universal Succinct Representations of Trees?.- Distortion Is Fixed Parameter Tractable.- Towards Optimal Range Medians.- B-Treaps: A Uniquely Represented Alternative to B-Trees.- Testing Fourier Dimensionality and Sparsity.- Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams.- Wireless Communication Is in APX.- The Ehrenfeucht-Silberger Problem.- Applications of Effective Probability Theory to Martin-Löf Randomness.- An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables.- Popular Mixed Matchings.- Factoring Groups Efficiently.- On Finding Dense Subgraphs.- Learning Halfspaces with Malicious Noise.- General Scheme for Perfect Quantum Network Coding with Free Classical Communication.- Greedy -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost.- Limits and Applications of Group Algebras for Parameterized Problems.- Sleep with Guilt and Work Faster to Minimize Flow Plus Energy.- Improved Bounds for Flow Shop Scheduling.- A 3/2-Approximation Algorithm for General Stable Marriage.- Limiting Negations in Formulas.- Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems.- Superhighness and Strong Jump Traceability.- Amortized Communication Complexity of Distributions.- The Number of Symbol Comparisons in QuickSort and QuickSelect.- Computing the Girth of a Planar Graph in O(n logn) Time.- Elimination Graphs.