Automata, Languages and Programming 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I /
| Συγγραφή απο Οργανισμό/Αρχή: | |
|---|---|
| Άλλοι συγγραφείς: | , , , |
| Μορφή: | Ηλεκτρονική πηγή Ηλ. βιβλίο |
| Γλώσσα: | English |
| Έκδοση: |
Berlin, Heidelberg :
Springer Berlin Heidelberg,
2006.
|
| Σειρά: | Lecture Notes in Computer Science,
4051 |
| Θέματα: | |
| Διαθέσιμο Online: | Full Text via HEAL-Link |
Πίνακας περιεχομένων:
- 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.
