LEADER 07295nam 22008295 450 001 996465854903316 005 20230406055039.0 010 $a3-540-35905-2 024 7 $a10.1007/11786986 035 $a(CKB)1000000000233041 035 $a(SSID)ssj0000316393 035 $a(PQKBManifestationID)11261618 035 $a(PQKBTitleCode)TC0000316393 035 $a(PQKBWorkID)10263683 035 $a(PQKB)10493684 035 $a(DE-He213)978-3-540-35905-0 035 $a(MiAaPQ)EBC3068063 035 $a(PPN)123136466 035 $a(EXLCZ)991000000000233041 100 $a20101221d2006 u| 0 101 0 $aeng 135 $aurnn#008mamaa 181 $ctxt 182 $cc 183 $acr 200 10$aAutomata, Languages and Programming$b[electronic resource] $e33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I /$fedited by Michele Bugliesi, Bart Preneel, Vladimiro Sassone, Ingo Wegener 205 $a1st ed. 2006. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2006. 215 $a1 online resource (XXIV, 732 p.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v4051 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a3-540-35904-4 320 $aIncludes bibliographical references and index. 327 $aInvited 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. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v4051 606 $aSoftware engineering 606 $aComputer science 606 $aComputer science?Mathematics 606 $aDiscrete mathematics 606 $aNumerical analysis 606 $aArtificial intelligence?Data processing 606 $aData structures (Computer science) 606 $aInformation theory 606 $aSoftware Engineering 606 $aTheory of Computation 606 $aDiscrete Mathematics in Computer Science 606 $aNumerical Analysis 606 $aData Science 606 $aData Structures and Information Theory 615 0$aSoftware engineering. 615 0$aComputer science. 615 0$aComputer science?Mathematics. 615 0$aDiscrete mathematics. 615 0$aNumerical analysis. 615 0$aArtificial intelligence?Data processing. 615 0$aData structures (Computer science). 615 0$aInformation theory. 615 14$aSoftware Engineering. 615 24$aTheory of Computation. 615 24$aDiscrete Mathematics in Computer Science. 615 24$aNumerical Analysis. 615 24$aData Science. 615 24$aData Structures and Information Theory. 676 $a005.1 702 $aBugliesi$b Michele$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aPreneel$b Bart$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aSassone$b Vladimiro$4edt$4http://id.loc.gov/vocabulary/relators/edt 702 $aWegener$b Ingo$4edt$4http://id.loc.gov/vocabulary/relators/edt 906 $aBOOK 912 $a996465854903316 996 $aAutomata, languages and programming$9339738 997 $aUNISA