default search action
33rd ICALP 2006: Venice, Italy
- Michele Bugliesi, Bart Preneel, Vladimiro Sassone, Ingo Wegener:
Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I. Lecture Notes in Computer Science 4051, Springer 2006, ISBN 3-540-35904-4
Invited Lectures
- Noga Alon, Asaf Shapira, Benny Sudakov:
Additive Approximation for Edge-Deletion Problems (Abstract). 1-2
Graph Theory I
- Martin Grohe
, Oleg Verbitsky
Testing Graph Isomorphism in Parallel by Playing a Game. 3-14 - Amin Coja-Oghlan, André Lanka:
The Spectral Gap of Random Graphs with Given Expected Degrees. 15-26 - Douglas E. Carroll, Ashish Goel, Adam Meyerson:
Embedding Bounded Bandwidth Graphs into l1. 27-37 - Martin E. Dyer
On Counting Homomorphisms to Directed Acyclic Graphs. 38-49
Quantum Computing
- Ben Reichardt:
Fault-Tolerance Threshold for a Distance-Three Quantum Code. 50-61 - Ronald de Wolf:
Lower Bounds on Matrix Rigidity Via a Quantum Argument. 62-71 - Frédéric Magniez, Dominic Mayers, Michele Mosca, Harold Ollivier:
Self-testing of Quantum Circuits. 72-83
Randomness
- Chia-Jung Lee, Chi-Jen Lu, Shi-Chun Tsai:
Deterministic Extractors for Independent-Symbol Sources. 84-95 - Jaikumar Radhakrishnan:
Gap Amplification in PCPs Using Lazy Random Walks. 96-107 - Magnus Bordewich
Stopping Times, Metrics and Approximate Counting. 108-119
Formal Languages
- Michal Kunc:
Algebraic Characterization of the Finite Power Property. 120-131 - Turlough Neary
P-completeness of Cellular Automaton Rule 110. 132-143 - Christos A. Kapoutsis
Small Sweeping 2NFAs Are Not Closed Under Complement. 144-156 - Mikolaj Bojanczyk, Mathias Samuelides, Thomas Schwentick, Luc Segoufin:
Expressive Power of Pebble Automata. 157-168
Approximation Algorithms I
- R. Ravi, Mohit Singh:
Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs. 169-180 - Naveen Garg
Better Algorithms for Minimizing Average Flow-Time on Related Machines. 181-190 - Kamalika Chaudhuri, Satish Rao, Samantha J. Riesenfeld
A Push-Relabel Algorithm for Approximating Degree Bounded MSTs. 191-201 - Satish Rao, Shuheng Zhou:
Edge Disjoint Paths in Moderately Connected Graphs. 202-213
Approximation Algorithms II
- Leah Epstein, Asaf Levin
A Robust APTAS for the Classical Bin Packing Problem. 214-225 - Subhash Khot, Ashok Kumar Ponnuswami:
Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion. 226-237 - Rolf Harren:
Approximating the Orthogonal Knapsack Problem for Hypercubes. 238-249
Graph Algorithms I
- Ramesh Hariharan, Telikepalli Kavitha, Kurt Mehlhorn:
A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs. 250-261 - Virginia Vassilevska, Ryan Williams
Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems. 262-273 - Piotr Sankowski:
Weighted Bipartite Matching in Matrix Multiplication Time. 274-285
Algorithms I
- Irene Finocchi
Optimal Resilient Sorting and Searching in the Presence of Memory Faults. 286-298 - Kurt Mehlhorn, Ralf Osbild, Michael Sagraloff:
Reliable and Efficient Computational Geometry Via Controlled Perturbation. 299-310 - Ioannis Caragiannis
Tight Bounds for Selfish and Greedy Load Balancing. 311-322
Complexity I
- Arist Kojevnikov, Dmitry Itsykson:
Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies. 323-334 - Lance Fortnow, John M. Hitchcock
Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws. 335-345 - Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. 346-357
Data Structures and Linear Algebra
- Richard Cole, Tsvi Kopelowitz, Moshe Lewenstein:
Suffix Trays and Suffix Trists: Structures for Faster Text Indexing. 358-369 - Alexander Golynski:
Optimal Lower Bounds for Rank and Select Indexes. 370-381 - Alexis C. Kaporis, Christos Makris
Dynamic Interpolation Search Revisited. 382-394 - Gudmund Skovbjerg Frandsen, Peter Frands Frandsen:
Dynamic Matrix Rank. 395-406
Graphs
- Xin He, Huaming Zhang:
Nearly Optimal Visibility Representations of Plane Graphs. 407-418 - Hristo N. Djidjev, Imrich Vrto:
Planar Crossing Numbers of Genus g Graphs. 419-430 - Toshihiro Fujito:
How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover. 431-442 - Guy Kortsarz, Zeev Nutov:
Tight Approximation Algorithm for Connectivity Augmentation Problems. 443-452
Complexity II
- Thanh Minh Hoang, Meena Mahajan, Thomas Thierauf:
On the Bipartite Unique Perfect Matching Problem. 453-464 - John M. Hitchcock
Comparing Reductions to NP-Complete Sets. 465-476 - Deeparnab Chakrabarty, Aranyak Mehta, Vijay V. Vazirani:
Design Is as Easy as Optimization. 477-488 - Xi Chen, Xiaotie Deng:
On the Complexity of 2D Discrete Fixed Point Problem. 489-500
Game Theory I
- Martin Gairing, Burkhard Monien, Karsten Tiemann:
Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions. 501-512 - Constantinos Daskalakis, Alex Fabrikant, Christos H. Papadimitriou:
The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games. 513-524 - Roberto Cominetti
Network Games with Atomic Players. 525-536
Algorithms II
- David Doty
Finite-State Dimension and Real Arithmetic. 537-547 - Andreas Björklund, Thore Husfeldt:
Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings. 548-559 - Paolo Ferragina
The Myriad Virtues of Wavelet Trees. 560-571
Game Theory II
- Dimitris Fotakis
Atomic Congestion Games Among Coalitions. 572-583 - Bruno Codenotti, Luis Rademacher, Kasturi R. Varadarajan:
Computing Equilibrium Prices in Exchange Economies with Tax Distortions. 584-595 - Vincenzo Auletta
New Constructions of Mechanisms with Verification. 596-607
Networks, Circuits and Regular Expressions
- Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky, Ronen Shabo:
On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations. 608-618 - Amos Korman, David Peleg:
Dynamic Routing Schemes for General Graphs. 619-630 - Kei Uchizawa
Energy Complexity and Entropy of Threshold Circuits. 631-642 - Philip Bille:
New Algorithms for Regular Expression Matching. 643-654
Fixed Parameter Complexity and Approximation Algorithms
- Dániel Marx:
A Parameterized View on Matroid Optimization Problems. 655-666 - Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Russell Schwartz
Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction. 667-678 - Georg Baier, Thomas Erlebach
Length-Bounded Cuts and Flows. 679-690
Graph Algorithms II
- Amin Coja-Oghlan:
An Adaptive Spectral Heuristic for Partitioning Random Graphs. 691-702 - Jin-yi Cai, Vinay Choudhary:
Some Results on Matchgates and Holographic Algorithms. 703-714 - Julián Mestre:
Weighted Popular Matchings. 715-726
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-01-13 01:11 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: