Automata, Languages and Programming [electronic resource] : 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I / edited by Michele Bugliesi, Bart Preneel, Vladimiro Sassone, Ingo Wegener.Material type: TextLanguage: English Series: Lecture Notes in Computer Science: 4051Publisher: Berlin, Heidelberg : Springer Berlin Heidelberg, 2006Description: XXIII, 729 p. Also available online. online resourceContent type: text Media type: computer Carrier type: online resourceISBN: 9783540359050Subject(s): Computer science | Software engineering | Data structures (Computer science) | Information theory | Electronic data processing | Computational complexity | Computer Science | Theory of Computation | Software Engineering/Programming and Operating Systems | Discrete Mathematics in Computer Science | Numeric Computing | Data Structures | Data Structures, Cryptology and Information TheoryAdditional physical formats: Printed edition:: No titleDDC classification: 004.0151 LOC classification: QA75.5-76.95Online resources: Click here to access online
Invited Lectures -- Additive Approximation for Edge-Deletion Problems (Abstract) -- Graph Theory I -- Testing Graph Isomorphism in Parallel by Playing a Game -- The Spectral Gap of Random Graphs with Given Expected Degrees -- Embedding Bounded Bandwidth Graphs into ?1 -- On Counting Homomorphisms to Directed Acyclic Graphs -- Quantum Computing -- Fault-Tolerance Threshold for a Distance-Three Quantum Code -- Lower Bounds on Matrix Rigidity Via a Quantum Argument -- Self-testing of Quantum Circuits -- Deterministic Extractors for Independent-Symbol Sources -- Randomness -- Gap Amplification in PCPs Using Lazy Random Walks -- Stopping Times, Metrics and Approximate Counting -- Formal Languages -- Algebraic Characterization of the Finite Power Property -- P-completeness of Cellular Automaton Rule 110 -- Small Sweeping 2NFAs Are Not Closed Under Complement -- Expressive Power of Pebble Automata -- Approximation Algorithms I -- Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs -- Better Algorithms for Minimizing Average Flow-Time on Related Machines -- A Push-Relabel Algorithm for Approximating Degree Bounded MSTs -- Edge Disjoint Paths in Moderately Connected Graphs -- Approximation Algorithms II -- A Robust APTAS for the Classical Bin Packing Problem -- Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion -- Approximating the Orthogonal Knapsack Problem for Hypercubes -- Graph Algorithms I -- A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs -- Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems -- Weighted Bipartite Matching in Matrix Multiplication Time -- Algorithms I -- Optimal Resilient Sorting and Searching in the Presence of Memory Faults -- Reliable and Efficient Computational Geometry Via Controlled Perturbation -- Tight Bounds for Selfish and Greedy Load Balancing -- Complexity I -- Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies -- Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws -- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies -- Data Structures and Linear Algebra -- Suffix Trays and Suffix Trists: Structures for Faster Text Indexing -- Optimal Lower Bounds for Rank and Select Indexes -- Dynamic Interpolation Search Revisited -- Dynamic Matrix Rank -- Graphs -- Nearly Optimal Visibility Representations of Plane Graphs -- Planar Crossing Numbers of Genus g Graphs -- How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover -- Tight Approximation Algorithm for Connectivity Augmentation Problems -- Complexity II -- On the Bipartite Unique Perfect Matching Problem -- Comparing Reductions to NP-Complete Sets -- Design Is as Easy as Optimization -- On the Complexity of 2D Discrete Fixed Point Problem -- Game Theory I -- Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions -- The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games -- Network Games with Atomic Players -- Algorithms II -- Finite-State Dimension and Real Arithmetic -- Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings -- The Myriad Virtues of Wavelet Trees -- Game Theory II -- Atomic Congestion Games Among Coalitions -- Computing Equilibrium Prices in Exchange Economies with Tax Distortions -- New Constructions of Mechanisms with Verification -- Networks, Circuits and Regular Expressions -- On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations -- Dynamic Routing Schemes for General Graphs -- Energy Complexity and Entropy of Threshold Circuits -- New Algorithms for Regular Expression Matching -- Fixed Parameter Complexity and Approximation Algorithms -- A Parameterized View on Matroid Optimization Problems -- Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction -- Length-Bounded Cuts and Flows -- Graph Algorithms II -- An Adaptive Spectral Heuristic for Partitioning Random Graphs -- Some Results on Matchgates and Holographic Algorithms -- Weighted Popular Matchings.
ICALP 2006, the 33rd edition of the International Colloquium on Automata, LanguagesandProgramming,washeldinVenice,Italy,July10–14,2006.ICALP is a series of annual conferences of the European Association for Theoretical ComputerScience(EATCS)which?rsttookplacein1972.Thisyear,theICALP programconsistedof the establishedtrackA (focusing on algorithms,automata, complexity and games) and track B (focusing on logic, semantics and theory of programming), and of the recently introduced track C (focusing on security and cryptography foundation). In response to the call for papers, the Program Committee received 407 s- missions, 230 for track A, 96 for track B and 81 for track C. Out of these, 109 papers were selected for inclusion in the scienti?c program: 61 papers for Track A, 24 for Track B and 24 for Track C. The selection was made by the Program Committee based on originality, quality, and relevance to theoretical computer science. The quality of the manuscripts was very high indeed, and several - serving papers had to be rejected. ICALP 2006 consisted of four invited lectures and the contributed papers. This volume of the proceedings contains all contributed papers presented at the conference in Track A, together with the paper by the invited speaker Noga Alon (Tel Aviv University, Israel). A companion volume contains all contributed paperspresentedinTrackBandTrackCtogetherwiththepapersbytheinvited speakers Cynthia Dwork (Microsoft Research, USA) and Prakash Panangaden (Mc Gill University, Canada). The programhad an additional invited lecture by Simon Peyton Jones (Microsoft Research, UK), which does not appear in the proceedings.