000 06926nam a22006615i 4500
001 978-3-540-35905-0
003 DE-He213
005 20240730200038.0
007 cr nn 008mamaa
008 101221s2006 gw | s |||| 0|eng d
020 _a9783540359050
_9978-3-540-35905-0
024 7 _a10.1007/11786986
_2doi
050 4 _aQA76.758
072 7 _aUMZ
_2bicssc
072 7 _aCOM051230
_2bisacsh
072 7 _aUMZ
_2thema
082 0 4 _a005.1
_223
245 1 0 _aAutomata, Languages and Programming
_h[electronic resource] :
_b33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I /
_cedited by Michele Bugliesi, Bart Preneel, Vladimiro Sassone, Ingo Wegener.
250 _a1st ed. 2006.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2006.
300 _aXXIV, 732 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v4051
505 0 _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 ComputationalGeometry 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.
650 0 _aSoftware engineering.
_94138
650 0 _aComputer science.
_99832
650 0 _aComputer science
_xMathematics.
_93866
650 0 _aDiscrete mathematics.
_912873
650 0 _aNumerical analysis.
_94603
650 0 _aArtificial intelligence
_xData processing.
_921787
650 0 _aData structures (Computer science).
_98188
650 0 _aInformation theory.
_914256
650 1 4 _aSoftware Engineering.
_94138
650 2 4 _aTheory of Computation.
_9161966
650 2 4 _aDiscrete Mathematics in Computer Science.
_931837
650 2 4 _aNumerical Analysis.
_94603
650 2 4 _aData Science.
_934092
650 2 4 _aData Structures and Information Theory.
_931923
700 1 _aBugliesi, Michele.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9161967
700 1 _aPreneel, Bart.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9161968
700 1 _aSassone, Vladimiro.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9161969
700 1 _aWegener, Ingo.
_eeditor.
_4edt
_4http://id.loc.gov/vocabulary/relators/edt
_9161970
710 2 _aSpringerLink (Online service)
_9161971
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783540359043
776 0 8 _iPrinted edition:
_z9783540826279
830 0 _aTheoretical Computer Science and General Issues,
_x2512-2029 ;
_v4051
_9161972
856 4 0 _uhttps://doi.org/10.1007/11786986
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cELN
999 _c95868
_d95868