@incollection{Alon-Shapira-Sudakov/06,
AUTHOR = {Alon, Noga and Shapira, Asaf and Sudakov, Benny},
TITLE = {Additive approximation for edge-deletion problems},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {1-2},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_1},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Grohe-Verbitsky/06,
AUTHOR = {Grohe, Martin and Verbitsky, Oleg},
TITLE = {Testing graph isomorphism in parallel by playing a game},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {3-14},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_2},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Coja-Oghlan-Lanka/06,
AUTHOR = {Coja-Oghlan, Amin and Lanka, Andr{\'e}},
TITLE = {The spectral gap of random graphs with given expected degrees},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {15-26},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_3},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Carroll-Goel-Meyerson/06,
AUTHOR = {Carroll, Douglas E. and Goel, Ashish and Meyerson, Adam},
TITLE = {Embedding bounded bandwidth graphs into $l_1$},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {27-37},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_4},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dyer-Goldberg-Paterson/06,
AUTHOR = {Dyer, Martin and Goldberg, Leslie Ann and Paterson, Mike},
TITLE = {On counting homomorphisms to directed acyclic graphs},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {38-49},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_5},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Reichardt/06,
AUTHOR = {Reichardt, Ben W.},
TITLE = {Fault-tolerance threshold for a distance-three quantum code},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {50-61},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_6},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{de_Wolf/06,
AUTHOR = {de Wolf, Ronald},
TITLE = {Lower bounds on matrix rigidity via a quantum argument},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {62-71},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_7},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Magniez-Mayers-Mosca-Ollivier/06,
AUTHOR = {Magniez, Fr{\'e}d{\'e}ric and Mayers, Dominic and Mosca, Michele and Ollivier, Harold},
TITLE = {Self-testing of quantum circuits},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {72-83},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_8},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Lee-Lu-Tsai/06,
AUTHOR = {Lee, Chia-Jung and Lu, Chi-Jen and Tsai, Shi-Chun},
TITLE = {Deterministic extractors for independent-symbol sources},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {84-95},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_9},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Radhakrishnan/06,
AUTHOR = {Radhakrishnan, Jaikumar},
TITLE = {Gap amplification in PCPs using lazy random walks},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {96-107},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_10},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bordewich-Dyer-Karpinski/06,
AUTHOR = {Bordewich, Magnus and Dyer, Martin and Karpinski, Marek},
TITLE = {Stopping times, metrics and approximate counting},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {108-119},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_11},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kunc/06,
AUTHOR = {Kunc, Michal},
TITLE = {Algebraic characterization of the finite power property},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {120-131},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_12},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Neary-Woods/06,
AUTHOR = {Neary, Turlough and Woods, Damien},
TITLE = {$P$-completeness of cellular automaton rule 110},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {132-143},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_13},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kapoutsis/06,
AUTHOR = {Kapoutsis, Christos A.},
TITLE = {Small sweeping 2NFAs are not closed under complement},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {144-156},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_14},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bojanczyk-Samuelides-Schwentick-Segoufin/06,
AUTHOR = {Boja{\'n}czyk, Miko{\l}aj and Samuelides, Mathias and Schwentick, Thomas and Segoufin, Luc},
TITLE = {Expressive power of pebble automata},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {157-168},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_15},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ravi-Singh/06,
AUTHOR = {Ravi, R. and Singh, Mohit},
TITLE = {Delegate and conquer: An $LP$-based approximation algorithm for minimum degree MSTs},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {169-180},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_16},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Garg-Kumar/06,
AUTHOR = {Garg, Naveen and Kumar, Amit},
TITLE = {Better algorithms for minimizing average flow-time on related machines},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {181-190},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_17},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chaudhuri-Rao-Riesenfeld-Talwar/06,
AUTHOR = {Chaudhuri, Kamalika and Rao, Satish and Riesenfeld, Samantha and Talwar, Kunal},
TITLE = {A push-relabel algorithm for approximating degree bounded MSTs},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {191-201},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_18},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Rao-Zhou/06,
AUTHOR = {Rao, Satish and Zhou, Shuheng},
TITLE = {Edge disjoint paths in moderately connected graphs},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {202-213},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_19},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Epstein-Levin/06,
AUTHOR = {Epstein, Leah and Levin, Asaf},
TITLE = {A robust APTAS for the classical bin packing problem},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {214-225},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_20},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Khot-Ponnuswami/06,
AUTHOR = {Khot, Subhash and Ponnuswami, Ashok Kumar},
TITLE = {Better inapproximability results for MaxClique, chromatic number and Min-3Lin-Deletion},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {226-237},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_21},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Harren/06,
AUTHOR = {Harren, Rolf},
TITLE = {Approximating the orthogonal knapsack problem for hypercubes},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {238-249},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_22},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hariharan-Kavitha-Mehlhorn/06,
AUTHOR = {Hariharan, Ramesh and Kavitha, Telikepalli and Mehlhorn, Kurt},
TITLE = {A faster deterministic algorithm for minimum cycle bases in directed graphs},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {250-261},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_23},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Vassilevska-Williams-Yuster/06,
AUTHOR = {Vassilevska, Virginia and Williams, Ryan and Yuster, Raphael},
TITLE = {Finding the smallest $H$-subgraph in real weighted graphs and related problems},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {262-273},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_24},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Sankowski/06,
AUTHOR = {Sankowski, Piotr},
TITLE = {Weighted bipartite matching in matrix multiplication time},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {274-285},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_25},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Finocchi-Grandoni-Italiano/06,
AUTHOR = {Finocchi, Irene and Grandoni, Fabrizio and Italiano, Giuseppe F.},
TITLE = {Optimal resilient sorting and searching in the presence of memory faults},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {286-298},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_26},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Mehlhorn-Osbild-Sagraloff/06,
AUTHOR = {Mehlhorn, Kurt and Osbild, Ralf and Sagraloff, Michael},
TITLE = {Reliable and efficient computational geometry via controlled perturbation},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {299-310},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_27},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Caragiannis-Flammini-Kaklamanis-Kanellopoulos-Moscardelli/06,
AUTHOR = {Caragiannis, Ioannis and Flammini, Michele and Kaklamanis, Christos and Kanellopoulos, Panagiotis and Moscardelli, Luca},
TITLE = {Tight bounds for selfish and greedy load balancing},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {311-322},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_28},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kojevnikov-Itsykson/06,
AUTHOR = {Kojevnikov, Arist and Itsykson, Dmitry},
TITLE = {Lower bounds of static Lov{\'a}sz-Schrijver calculus proofs for Tseitin tautologies},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {323-334},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_29},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fortnow-Hitchcock-Pavan-Vinodchandran-Wang/06,
AUTHOR = {Fortnow, Lance and Hitchcock, John M. and Pavan, A. and Vinodchandran, N.V. and Wang, Fengming},
TITLE = {Extracting Kolmogorov complexity with applications to dimension zero-one laws},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {335-345},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_30},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gopalan-Kolaitis-Maneva-Papadimitriou/06,
AUTHOR = {Gopalan, Parikshit and Kolaitis, Phokion G. and Maneva, Elitza N. and Papadimitriou, Christos H.},
TITLE = {The connectivity of Boolean satisfiability: Computational and structural dichotomies},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {346-357},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_31},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cole-Kopelowitz-Lewenstein/06,
AUTHOR = {Cole, Richard and Kopelowitz, Tsvi and Lewenstein, Moshe},
TITLE = {Suffix trays and suffix trists: Structures for faster text indexing},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {358-369},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_32},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Golynski/06,
AUTHOR = {Golynski, Alexander},
TITLE = {Optimal lower bounds for rank and select indexes},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {370-381},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_33},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kaporis-Makris-Sioutas-Tsakalidis-Tsichlas-Zaroliagis/06,
AUTHOR = {Kaporis, Alexis and Makris, Christos and Sioutas, Spyros and Tsakalidis, Athanasios and Tsichlas, Kostas and Zaroliagis, Christos},
TITLE = {Dynamic interpolation search revisited},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {382-394},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_34},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Frandsen-Frandsen/06,
AUTHOR = {Frandsen, Gudmund Skovbjerg and Frandsen, Peter Frands},
TITLE = {Dynamic matrix rank},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {395-406},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_35},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{He-Zhang/06,
AUTHOR = {He, Xin and Zhang, Huaming},
TITLE = {Nearly optimal visibility representations of plane graphs},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {407-418},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_36},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Djidjev-Vrto/06,
AUTHOR = {Djidjev, Hristo and Vrt'o, Imrich},
TITLE = {Planar crossing numbers of genus $g$ graphs},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {419-430},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_37},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fujito/06,
AUTHOR = {Fujito, Toshihiro},
TITLE = {How to trim an MST: A 2-approximation algorithm for minimum cost tree cover},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {431-442},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_38},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kortsarz-Nutov/06,
AUTHOR = {Kortsarz, Guy and Nutov, Zeev},
TITLE = {Tight approximation algorithm for connectivity augmentation problems},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {443-452},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_39},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hoang-Mahajan-Thierauf/06,
AUTHOR = {Hoang, Thanh Minh and Mahajan, Meena and Thierauf, Thomas},
TITLE = {On the bipartite unique perfect matching problem},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {453-464},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_40},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hitchcock-Pavan/06,
AUTHOR = {Hitchcock, John M. and Pavan, A.},
TITLE = {Comparing reductions to $NP$-complete sets},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {465-476},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_41},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chakrabarty-Mehta-Vazirani/06,
AUTHOR = {Chakrabarty, Deeparnab and Mehta, Aranyak and Vazirani, Vijay V.},
TITLE = {Design is as easy as optimization},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {477-488},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_42},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chen-Deng/06,
AUTHOR = {Chen, Xi and Deng, Xiaotie},
TITLE = {On the complexity of 2D discrete fixed point problem},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {489-500},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_43},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gairing-Monien-Tiemann/06,
AUTHOR = {Gairing, Martin and Monien, Burkhard and Tiemann, Karsten},
TITLE = {Routing (un-) splittable flow in games with player-specific linear latency functions},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {501-512},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_44},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Daskalakis-Fabrikant-Papadimitriou/06,
AUTHOR = {Daskalakis, Constantinos and Fabrikant, Alex and Papadimitriou, Christos H.},
TITLE = {The game world is flat: The complexity of Nash equilibria in succinct games},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {513-524},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_45},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cominetti-Correa-Stier-Moses/06,
AUTHOR = {Cominetti, Roberto and Correa, Jos{\'e} R. and Stier-Moses, Nicol{\'a}s E.},
TITLE = {Network games with atomic players},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {525-536},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_46},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Doty-Lutz-Nandakumar/06,
AUTHOR = {Doty, David and Lutz, Jack H. and Nandakumar, Satyadev},
TITLE = {Finite-state dimension and real arithmetic},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {537-547},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_47},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bjorklund-Husfeldt/06,
AUTHOR = {Bj{\"o}rklund, Andreas and Husfeldt, Thore},
TITLE = {Exact algorithms for exact satisfiability and number of perfect matchings},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {548-559},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_48},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ferragina-Giancarlo-Manzini/06,
AUTHOR = {Ferragina, Paolo and Giancarlo, Raffaele and Manzini, Giovanni},
TITLE = {The myriad virtues of Wavelet Trees},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {560-571},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_49},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fotakis-Kontogiannis-Spirakis/06,
AUTHOR = {Fotakis, Dimitris and Kontogiannis, Spyros and Spirakis, Paul},
TITLE = {Atomic congestion games among coalitions},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {572-583},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_50},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Codenotti-Rademacher-Varadarajan/06,
AUTHOR = {Codenotti, Bruno and Rademacher, Luis and Varadarajan, Kasturi},
TITLE = {Computing equilibrium prices in exchange economies with tax distortions},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {584-595},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_51},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Auletta-De_Prisco-Penna-Persiano-Ventre/06,
AUTHOR = {Auletta, Vincenzo and De Prisco, Roberto and Penna, Paolo and Persiano, Giuseppe and Ventre, Carmine},
TITLE = {New constructions of mechanisms with verification},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {596-607},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_52},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fiat-Kaplan-Levy-Olonetsky-Shabo/06,
AUTHOR = {Fiat, Amos and Kaplan, Haim and Levy, Meital and Olonetsky, Svetlana and Shabo, Ronen},
TITLE = {On the price of stability for designing undirected networks with fair cost allocations},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {608-618},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_53},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Korman-Peleg/06,
AUTHOR = {Korman, Amos and Peleg, David},
TITLE = {Dynamic routing schemes for general graphs},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {619-630},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_54},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Uchizawa-Douglas-Maass/06,
AUTHOR = {Uchizawa, Kei and Douglas, Rodney and Maass, Wolfgang},
TITLE = {Energy complexity and entropy of threshold circuits},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {631-642},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_55},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bille/06,
AUTHOR = {Bille, Philip},
TITLE = {New algorithms for regular expression matching},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {643-654},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_56},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Marx/06,
AUTHOR = {Marx, D{\'a}niel},
TITLE = {A parameterized view on matroid optimization problems},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {655-666},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_57},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Blelloch-Dhamdhere-Halperin-Ravi-Schwartz-Sridhar/06,
AUTHOR = {Blelloch, Guy E. and Dhamdhere, Kedar and Halperin, Eran and Ravi, R. and Schwartz, Russell and Sridhar, Srinath},
TITLE = {Fixed parameter tractability of binary near-perfect phylogenetic tree reconstruction},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {667-678},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_58},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Baier-Erlebach-Hall-Kohler-Schilling-Skutella/06,
AUTHOR = {Baier, Georg and Erlebach, Thomas and Hall, Alexander and K{\"o}hler, Ekkehard and Schilling, Heiko and Skutella, Martin},
TITLE = {Length-bounded cuts and flows},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {679-690},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_59},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Coja-Oghlan/06,
AUTHOR = {Coja-Oghlan, Amin},
TITLE = {An adaptive spectral heuristic for partitioning random graphs},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {691-702},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_60},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cai-Choudhary/06,
AUTHOR = {Cai, Jin-Yi and Choudhary, Vinay},
TITLE = {Some results on matchgates and holographic algorithms},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {703-714},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_61},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Mestre/06a,
AUTHOR = {Mestre, Juli{\'a}n},
TITLE = {Weighted popular matchings},
BOOKTITLE = {Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP'2006, Part I (Venice, Italy, July 10-14, 2006)},
SERIES = {LNCS},
VOLUME = {4051},
PAGES = {715-726},
YEAR = {2006},
EDITOR = {Bugliesi, Michele and Preneel, Bart and Sassone, Vladimiro and Wegener, Ingo},
URL = {http://dx.doi.org/10.1007/11786986_62},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}