20. STACS 2003: Berlin, Germany
- Helmut Alt, Michel Habib:
STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27 - March 1, 2003, Proceedings. Lecture Notes in Computer Science 2607, Springer 2003, ISBN 3-540-00623-0
Invited Papers
Contributed Papers
- Ching-Chi Lin, Hsueh-I Lu, I-Fan Sun:
Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer. 14-25 - Ileana Streinu, Sue Whitesides:
Rectangle Visibility Graphs: Characterization, Construction, and Compaction. 26-37 - Prosenjit Bose, Anil Maheshwari, Giri Narasimhan, Michiel H. M. Smid, Norbert Zeh:
Approximating Geometric Bottleneck Shortest Paths. 38-49 - Pascal Tesson, Denis Thérien:
Complete Classifications for the Communication Complexity of Regular Languages. 62-73 - Juhani Karhumäki, Michel Latteux, Ion Petre:
The Commutation with Codes and Ternary Sets of Words. 74-84 - Guillem Godoy, Ashish Tiwari, Rakesh M. Verma:
On the Confluence of Linear Shallow Term Rewrite Systems. 85-96 - Dariusz R. Kowalski, Andrzej Pelc:
Faster Deterministic Broadcasting in Ad Hoc Radio Networks. 109-120 - Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk:
Private Computations in Networks: Topology versus Randomness. 121-132 - Thomas Erlebach, Stamatis Stefanakos:
On Shortest-Path All-Optical Networks without Wavelength Conversion Requirements. 133-144 - Xizhong Zheng, Robert Rettinger, Burchard von Braunmühl:
On the Effective Jordan Decomposability. 167-178 - Lucian Ilie, Baozhen Shan, Sheng Yu:
Fast Algorithms for Extended Regular Expression Matching and Searching. 179-190 - Veli Mäkinen, Gonzalo Navarro, Esko Ukkonen:
Algorithms for Transposition Invariant String Matching. 191-202 - Anton Mityagin:
On the Complexity of Finding a Local Maximum of Functions on Discrete Planar Subsets. 203-211 - Nikhil Bansal, Kedar Dhamdhere, Jochen Könemann, Amitabh Sinha:
Non-clairvoyant Scheduling for Minimizing Mean Slowdown. 260-270 - Dimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul G. Spirakis:
Space Efficient Hash Tables with Worst Case Constant Access Time. 271-282 - Hervé Brönnimann, Frédéric Cazals, Marianne Durand:
Randomized Jumplists: A Jump-and-Walk Dictionary Data Structure. 283-294 - Beate Bollig:
Complexity Theoretical Results on Nondeterministic Graph-Driven Read-Once Branching Programs. 295-306 - Martin Sauerhoff:
Randomness versus Nondeterminism for Read-Once and Read- k Branching Programs. 307-318 - Ricard Gavaldà, Denis Thérien:
Algebraic Characterizations of Small Classes of Boolean Functions. 331-342 - John Hershberger, Subhash Suri, Amit M. Bhosle:
On the Difficulty of Some Shortest Path Problems. 343-354 - Tomás Feder, Adam Meyerson, Rajeev Motwani, Liadan O'Callaghan, Rina Panigrahy:
Representing Graph Metrics with Fewest Edges. 355-366 - Tomás Feder, Rajeev Motwani, Liadan O'Callaghan, Chris Olston, Rina Panigrahy:
Computing Shortest Paths with Uncertainty. 367-378 - Robert W. Irving, David Manlove, Sandy Scott:
Strong Stability in the Hospitals/Residents Problem. 439-450 - Arnaud Durand, Miki Hermann:
The Inference Problem for Propositional Circumscription of Affine Formulas Is coNP-Complete. 451-462 - Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse:
An Information-Theoretic Upper Bound of Planar Graphs Using Triangulation. 499-510 - Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara:
Competing Provers Yield Improved Karp-Lipton Collapse Results. 535-546 - Pierre McKenzie, Klaus W. Wagner:
The Complexity of Membership Problems for Circuits over Sets of Natural Numbers. 571-582 - Wil Michiels, Jan H. M. Korst, Emile H. L. Aarts, Jan van Leeuwen:
Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem. 583-595 - Malik Magdon-Ismail, Costas Busch, Mukkai S. Krishnamoorthy:
Cake-Cutting Is Not a Piece of Cake. 596-607 - Amr Elmasry, Michael L. Fredman:
Adaptive Sorting and the Information Theoretic Lower Bound. 654-662 - Henrik Björklund, Sven Sandberg, Sergei G. Vorobyov:
A Discrete Subexponential Algorithm for Parity Games. 663-674 - Michael Backes, Christian Jacobi:
Cryptographically Sound and Machine-Assisted Verification of Security Protocols. 675-686 - Véronique Bruyère, Emmanuel Dall'Olio, Jean-François Raskin:
Durations, Parametric Model-Checking in Timed Automata with Presburger Arithmetic. 687-698