Theory of Computing Systems, Volume 49

Volume 49, Number 1, July 2011

• Marios Mavronicolas:
  Preface: Algorithmic Game Theory. 1-2
  
• Johanne Cohen, Christoph Dürr, Nguyen Kim Thang:
  Non-clairvoyant Scheduling Games. 3-23
  
• Vittorio Bilò, Angelo Fanelli, Michele Flammini, Luca Moscardelli:
  Performance of One-Round Walks in Linear Congestion Games. 24-45
  
• Tobias Harks, Max Klimm, Rolf H. Möhring:
  Characterizing the Existence of Potential Functions in Weighted Congestion Games. 46-70
  
• Ronald Koch, Martin Skutella:
  Nash Equilibria and the Price of Anarchy for Flows over Time. 71-97
  
• Elliot Anshelevich, Bugra Caskurlu:
  Price of Stability in Survivable Network Design. 98-138
  
• Felix Brandt, Markus Brill, Felix A. Fischer, Jan Hoffmann:
  The Computational Complexity of Weak Saddles. 139-161
  
• Felix Brandt, Markus Brill, Felix A. Fischer, Paul Harrenstein:
  On the Complexity of Iterated Weak Dominance in Constant-Sum Games. 162-181
  
• Hyunwoo Jung, Kyung-Yong Chwa:
  The Balloon Popping Problem Revisited: Lower and Upper Bounds. 182-195
  
• Clemens Thielen, Sven Oliver Krumke:
  Truthful Mechanisms for Selfish Routing and Two-Parameter Agents. 196-223
  

Volume 49, Number 2, August 2011

• Andrei S. Morozov, Klaus W. Wagner:
  Editorial. 225-226
  
• Daniil Musatov, Andrei E. Romashchenko, Alexander Shen:
  Variations on Muchnik's Conditional Complexity Theorem. 227-245
  
• B. V. Raghavendra Rao, Jayalal M. N. Sarma:
  On the Complexity of Matroid Isomorphism Problem. 246-272
  
• Magnus Wahlström:
  New Plain-Exponential Time Classes for Graph Homomorphism. 273-282
  
• Niko Haubold, Markus Lohrey:
  Compressed Word Problems in HNN-extensions and Amalgamated Products. 283-305
  
• Galina Jirásková:
  Concatenation of Regular Languages and Descriptional Complexity. 306-318
  
• Artur Jez, Alexander Okhotin:
  One-Nonterminal Conjunctive Grammars over a Unary Alphabet. 319-342
  
• Maurice J. Jansen:
  Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials. 343-354
  
• Christian Choffrut, Juhani Karhumäki:
  Unique Decipherability in the Monoid of Languages: An Application of Rational Relations. 355-364
  
• Albert Atserias, Mikolaj Bojanczyk, Balder ten Cate, Ronald Fagin, Floris Geerts, Kenneth Ross:
  Foreword. 365-366
  
• Bogdan Cautis, Alin Deutsch, Nicola Onose:
  Querying Data Sources that Export Infinite Sets of Views. 367-428
  
• Todd J. Green:
  Containment of Conjunctive Queries on Annotated Relations. 429-459
  
• Todd J. Green, Zachary G. Ives, Val Tannen:
  Reconcilable Differences. 460-488
  
• Marcelo Arenas, Pablo Barceló, Juan L. Reutter:
  Query Languages for Data Exchange: Beyond Unions of Conjunctive Queries. 489-564
  

Volume 49, Number 3, October 2011

• Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Henk Meijer:
  Area, Curve Complexity, and Crossing Resolution of Non-Planar Graph Drawings. 565-575
  
• Maw-Shang Chang, Chuang-Chieh Lin, Peter Rossmanith:
  A Property Tester for Tree-Likeness of Quartet Topologies. 576-587
  
• Chien-Hung Lin, Jia Jie Liu, Yue-Li Wang, William Chung-Kung Yen:
  The Hub Number of Sierpiński-Like Graphs. 588-600
  
• Ryan C. Harkins, John M. Hitchcock:
  Dimension, Halfspaces, and the Density of Hard Sets. 601-614
  
• Davide Bilò, Luca Forlizzi, Guido Proietti:
  Approximating the Metric TSP in Linear Time. 615-631
  
• Akitoshi Kawamura:
  Generalized Semimagic Squares for Digital Halftoning. 632-638
  
• Marcelo Arenas, Pablo Barceló, Leonid Libkin:
  Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization. 639-670
  

Volume 49, Number 4, November 2011

• Michael A. Bender, Seth Gilbert:
  Guest Editorial: Parallelism in Algorithms and Architectures. 671
  
• Patrik Floréen, Marja Hassinen, Joel Kaasinen, Petteri Kaski, Topi Musto, Jukka Suomela:
  Local Approximability of Max-Min and Min-Max Linear Programs. 672-697
  
• Hagit Attiya, Eshcar Hillel, Alessia Milani:
  Inherent Limitations on Disjoint-Access Parallel Implementations of Transactional Memory. 698-719
  
• Aviv Nisgav, Boaz Patt-Shamir:
  Finding Similar Users in Social Networks. 720-737
  
• Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda, Prasad Raghavendra:
  Buffer Management for Colored Packets with Deadlines. 738-756
  
• MohammadHossein Bateni, Lukasz Golab, MohammadTaghi Hajiaghayi, Howard J. Karloff:
  Scheduling to Minimize Staleness and Stretch in Real-Time Data Warehouses. 757-780
  
• Fabian Kuhn, Thomas Locher, Rotem Oshman:
  Gradient Clock Synchronization in Dynamic Networks. 781-816
  
• Ho-Leung Chan, Jeff Edmonds, Kirk Pruhs:
  Speed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessor. 817-833
  
• Harald Räcke, Adi Rosén:
  Approximation Algorithms for Time-Constrained Scheduling on Line Networks. 834-856
  

Last update Wed May 22 18:07:12 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page