Michele Bugliesi, Bart Preneel, Vladimiro Sassone, Ingo Wegener
Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, Part I
ICALP (1), 2006.

@proceedings{ICALP-v1-2006,
	address       = "Venice, Italy",
	editor        = "Michele Bugliesi and Bart Preneel and Vladimiro Sassone and Ingo Wegener",
	isbn          = "3-540-35904-4",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, Part I}",
	volume        = 4051,
	year          = 2006,
}

Contents (62 items)

11 ×#graph
9 ×#algorithm
8 ×#problem
7 ×#approximate
7 ×#bound
5 ×#game studies
4 ×#complexity
4 ×#on the
3 ×#matrix
3 ×#performance

ICALP-v1-2006-AlonSS #approximate #problem

Additive Approximation for Edge-Deletion Problems (NA, AS, BS), pp. 1–2.

ICALP-v1-2006-GroheV #game studies #graph #morphism #parallel #testing

Testing Graph Isomorphism in Parallel by Playing a Game (MG, OV), pp. 3–14.

ICALP-v1-2006-Coja-OghlanL #graph #random

The Spectral Gap of Random Graphs with Given Expected Degrees (ACO, AL), pp. 15–26.

ICALP-v1-2006-CarrollGM #bound #graph

Embedding Bounded Bandwidth Graphs into l1 (DEC, AG, AM), pp. 27–37.

ICALP-v1-2006-DyerGP #graph #morphism #on the

On Counting Homomorphisms to Directed Acyclic Graphs (MED, LAG, MP), pp. 38–49.

ICALP-v1-2006-Reichardt #fault tolerance #quantum

Fault-Tolerance Threshold for a Distance-Three Quantum Code (BR), pp. 50–61.

ICALP-v1-2006-Wolf #bound #matrix #quantum

Lower Bounds on Matrix Rigidity Via a Quantum Argument (RdW), pp. 62–71.

ICALP-v1-2006-MagniezMMO #quantum #self

Self-testing of Quantum Circuits (FM, DM, MM, HO), pp. 72–83.

ICALP-v1-2006-LeeLT #independence

Deterministic Extractors for Independent-Symbol Sources (CJL, CJL, SCT), pp. 84–95.

ICALP-v1-2006-Radhakrishnan #lazy evaluation #random #using

Gap Amplification in PCPs Using Lazy Random Walks (JR), pp. 96–107.

ICALP-v1-2006-BordewichDK #approximate #metric

Stopping Times, Metrics and Approximate Counting (MB, MED, MK), pp. 108–119.

ICALP-v1-2006-Kunc #algebra #finite

Algebraic Characterization of the Finite Power Property (MK), pp. 120–131.

ICALP-v1-2006-NearyW #automaton

P-completeness of Cellular Automaton Rule 110 (TN, DW), pp. 132–143.

ICALP-v1-2006-Kapoutsis

Small Sweeping 2NFAs Are Not Closed Under Complement (CAK), pp. 144–156.

ICALP-v1-2006-BojanczykSSS #automaton #power of

Expressive Power of Pebble Automata (MB, MS, TS, LS), pp. 157–168.

ICALP-v1-2006-RaviS #algorithm #approximate

Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs (RR, MS), pp. 169–180.

ICALP-v1-2006-GargK #algorithm

Better Algorithms for Minimizing Average Flow-Time on Related Machines (NG, AK), pp. 181–190.

ICALP-v1-2006-ChaudhuriRRT #algorithm #approximate #bound

A Push-Relabel Algorithm for Approximating Degree Bounded MSTs (KC, SR, SR, KT), pp. 191–201.

ICALP-v1-2006-RaoZ #graph

Edge Disjoint Paths in Moderately Connected Graphs (SR, SZ), pp. 202–213.

ICALP-v1-2006-EpsteinL #problem #robust

A Robust APTAS for the Classical Bin Packing Problem (LE, AL), pp. 214–225.

ICALP-v1-2006-KhotP #clique

Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion (SK, AKP), pp. 226–237.

ICALP-v1-2006-Harren #approximate #orthogonal #problem

Approximating the Orthogonal Knapsack Problem for Hypercubes (RH), pp. 238–249.

ICALP-v1-2006-HariharanKM #algorithm #graph #performance

A Faster Deterministic Algorithm for Minimum Cycle Bases in Directed Graphs (RH, TK, KM), pp. 250–261.

ICALP-v1-2006-VassilevskaWY #graph #problem

Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems (VV, RW, RY), pp. 262–273.

ICALP-v1-2006-Sankowski #matrix #multi

Weighted Bipartite Matching in Matrix Multiplication Time (PS), pp. 274–285.

ICALP-v1-2006-FinocchiGI #fault #memory management #sorting

Optimal Resilient Sorting and Searching in the Presence of Memory Faults (IF, FG, GFI), pp. 286–298.

ICALP-v1-2006-MehlhornOS #geometry #performance #reliability

Reliable and Efficient Computational Geometry Via Controlled Perturbation (KM, RO, MS), pp. 299–310.

ICALP-v1-2006-CaragiannisFKKM #bound

Tight Bounds for Selfish and Greedy Load Balancing (IC, MF, CK, PK, LM), pp. 311–322.

ICALP-v1-2006-KojevnikovI #bound #calculus #proving

Lower Bounds of Static Lovász-Schrijver Calculus Proofs for Tseitin Tautologies (AK, DI), pp. 323–334.

ICALP-v1-2006-FortnowHPVW #complexity

Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws (LF, JMH, AP, NVV, FW), pp. 335–345.

ICALP-v1-2006-GopalanKMP #satisfiability

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies (PG, PGK, ENM, CHP), pp. 346–357.

ICALP-v1-2006-ColeKL #performance

Suffix Trays and Suffix Trists: Structures for Faster Text Indexing (RC, TK, ML), pp. 358–369.

ICALP-v1-2006-Golynski #bound #rank

Optimal Lower Bounds for Rank and Select Indexes (AG), pp. 370–381.

ICALP-v1-2006-KaporisMSTTZ #revisited

Dynamic Interpolation Search Revisited (ACK, CM, SS, AKT, KT, CDZ), pp. 382–394.

ICALP-v1-2006-FrandsenF #matrix #rank

Dynamic Matrix Rank (GSF, PFF), pp. 395–406.

ICALP-v1-2006-HeZ #graph

Nearly Optimal Visibility Representations of Plane Graphs (XH, HZ), pp. 407–418.

ICALP-v1-2006-DjidjevV #graph

Planar Crossing Numbers of Genus g Graphs (HD, IV), pp. 419–430.

ICALP-v1-2006-Fujito #algorithm #approximate #how

How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover (TF), pp. 431–442.

ICALP-v1-2006-KortsarzN #algorithm #approximate #problem

Tight Approximation Algorithm for Connectivity Augmentation Problems (GK, ZN), pp. 443–452.

ICALP-v1-2006-HoangMT #on the #problem

On the Bipartite Unique Perfect Matching Problem (TMH, MM, TT), pp. 453–464.

ICALP-v1-2006-HitchcockP #reduction #set

Comparing Reductions to NP-Complete Sets (JMH, AP), pp. 465–476.

ICALP-v1-2006-ChakrabartyMV #design #optimisation

Design Is as Easy as Optimization (DC, AM, VVV), pp. 477–488.

ICALP-v1-2006-ChenD #2d #complexity #fixpoint #on the #problem

On the Complexity of 2D Discrete Fixed Point Problem (XC, XD), pp. 489–500.

ICALP-v1-2006-GairingMT #game studies #latency #linear

Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions (MG, BM, KT), pp. 501–512.

ICALP-v1-2006-DaskalakisFP #complexity #game studies #nash

The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games (CD, AF, CHP), pp. 513–524.

ICALP-v1-2006-CominettiCM #game studies #network

Network Games with Atomic Players (RC, JRC, NESM), pp. 525–536.

ICALP-v1-2006-DotyLN #finite

Finite-State Dimension and Real Arithmetic (DD, JHL, SN), pp. 537–547.

ICALP-v1-2006-BjorklundH #algorithm #satisfiability

Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings (AB, TH), pp. 548–559.

ICALP-v1-2006-FerraginaGM

The Myriad Virtues of Wavelet Trees (PF, RG, GM), pp. 560–571.

ICALP-v1-2006-FotakisKS #game studies

Atomic Congestion Games Among Coalitions (DF, SCK, PGS), pp. 572–583.

ICALP-v1-2006-CodenottiRV #equilibrium

Computing Equilibrium Prices in Exchange Economies with Tax Distortions (BC, LR, KRV), pp. 584–595.

ICALP-v1-2006-AulettaPPPV #verification

New Constructions of Mechanisms with Verification (VA, RDP, PP, GP, CV), pp. 596–607.

ICALP-v1-2006-FiatKLOS #design #network #on the

On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations (AF, HK, ML, SO, RS), pp. 608–618.

ICALP-v1-2006-KormanP #graph

Dynamic Routing Schemes for General Graphs (AK, DP), pp. 619–630.

ICALP-v1-2006-UchizawaDM #complexity #energy

Energy Complexity and Entropy of Threshold Circuits (KU, RJD, WM), pp. 631–642.

ICALP-v1-2006-Bille #algorithm #regular expression

New Algorithms for Regular Expression Matching (PB), pp. 643–654.

ICALP-v1-2006-Marx #optimisation #problem

A Parameterized View on Matroid Optimization Problems (DM), pp. 655–666.

ICALP-v1-2006-BlellochDHRSS #parametricity #re-engineering

Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction (GEB, KD, EH, RR, RS, SS), pp. 667–678.

ICALP-v1-2006-BaierEHKSS #bound

Length-Bounded Cuts and Flows (GB, TE, AH, EK, HS, MS), pp. 679–690.

ICALP-v1-2006-Coja-Oghlan #adaptation #clustering #graph #heuristic #random

An Adaptive Spectral Heuristic for Partitioning Random Graphs (ACO), pp. 691–702.

ICALP-v1-2006-CaiC #algorithm #artificial reality

Some Results on Matchgates and Holographic Algorithms (JyC, VC), pp. 703–714.

ICALP-v1-2006-Mestre

Weighted Popular Matchings (JM), pp. 715–726.