@article{Cohen-Durr-Kim/11,
AUTHOR = {Cohen, Johanne and D{\"u}rr, Christoph and Kim, Thang Nguyen},
TITLE = {Non-clairvoyant scheduling games},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {1},
PAGES = {3-23},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/k1285t28283mg431/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Bilo-Fanelli-Flammini-Moscardelli/11a,
AUTHOR = {Bil{\`o}, Vittorio and Fanelli, Angelo and Flammini, Michele and Moscardelli, Luca},
TITLE = {Performance of one-round walks in linear congestion games},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {1},
PAGES = {24-45},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/030767486r164337/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Harks-Klimm-Mohring/11,
AUTHOR = {Harks, Tobias and Klimm, Max and M{\"o}hring, Rolf H.},
TITLE = {Characterizing the existence of potential functions in weighted congestion games},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {1},
PAGES = {46-70},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/c5776620830572uv/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Koch-Skutella/11,
AUTHOR = {Koch, Ronald and Skutella, Martin},
TITLE = {Nash equilibria and the price of anarchy for flows over time},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {1},
PAGES = {71-97},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/nnl4qm81323273m7/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Anshelevich-Caskurlu/11a,
AUTHOR = {Anshelevich, Elliot and Caskurlu, Bugra},
TITLE = {Price of stability in survivable network design},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {1},
PAGES = {98-138},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/r888188517w64273/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Brandt-Brill-Fischer-Hoffmann/11,
AUTHOR = {Brandt, Felix and Brill, Markus and Fischer, Felix and Hoffmann, Jan},
TITLE = {The computational complexity of weak saddles},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {1},
PAGES = {139-161},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/4t302681437t614g/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Brandt-Brill-Fischer-Harrenstein/11,
AUTHOR = {Brandt, Felix and Brill, Markus and Fischer, Felix and Harrenstein, Paul},
TITLE = {On the complexity of iterated weak dominance in constant-sum games},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {1},
PAGES = {162-181},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/t275351nq5060557/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Jung-Chwa/11,
AUTHOR = {Jung, Hyunwoo and Chwa, Kyung-Yong},
TITLE = {The balloon popping problem revisited: Lower and upper bounds},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {1},
PAGES = {182-195},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/qw5377512nw22j06/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Thielen-Krumke/11,
AUTHOR = {Thielen, Clemens and Krumke, Sven O.},
TITLE = {Truthful mechanisms for selfish routing and two-parameter agents},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {1},
PAGES = {196-223},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/t68nr2016u580725/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Musatov-Romashchenko-Shen/11,
AUTHOR = {Musatov, Daniil and Romashchenko, Andrei and Shen, Alexander},
TITLE = {Variations on Muchnik's conditional complexity theorem},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {2},
PAGES = {227-245},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/hh5588v25l264w03/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Raghavendra_Rao-Sarma/11,
AUTHOR = {Raghavendra Rao, B.V. and Sarma, M.N. Jayalal},
TITLE = {On the complexity of matroid isomorphism problem},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {2},
PAGES = {246-272},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/j28577r053t05440/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Wahlstrom/11,
AUTHOR = {Wahlstr{\"o}m, Magnus},
TITLE = {New plain-exponential time classes for graph homomorphism},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {2},
PAGES = {273-282},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/647u6330q1k6g817/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Haubold-Lohrey/11,
AUTHOR = {Haubold, Niko and Lohrey, Markus},
TITLE = {Compressed word problems in HNN-extensions and amalgamated products},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {2},
PAGES = {283-305},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/q420878vx284586p/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Jiraskova/11a,
AUTHOR = {Jir{\'a}skov{\'a}, Galina},
TITLE = {Concatenation of regular languages and descriptional complexity},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {2},
PAGES = {306-318},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/05m2178608242185/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Jez-Okhotin/11a,
AUTHOR = {Je{\.z}, Artur and Okhotin, Alexander},
TITLE = {One-nonterminal conjunctive grammars over a unary alphabet},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {2},
PAGES = {319-342},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/9556803208n2v578/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Jansen/11,
AUTHOR = {Jansen, Maurice},
TITLE = {Lower bounds for the determinantal complexity of explicit low degree polynomials},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {2},
PAGES = {343-354},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/943808724688mq10/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Choffrut-Karhumaki/11,
AUTHOR = {Choffrut, Christian and Karhum{\"a}ki, Juhani},
TITLE = {Unique decipherability in the monoid of languages: An application of rational relations},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {2},
PAGES = {355-364},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/g447685884lt3278/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Cautis-Deutsch-Onose/11,
AUTHOR = {Cautis, Bogdan and Deutsch, Alin and Onose, Nicola},
TITLE = {Querying data sources that export infinite sets of views},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {2},
PAGES = {367-428},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/k562088470237l98/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Green/11,
AUTHOR = {Green, Todd J.},
TITLE = {Containment of conjunctive queries on annotated relations},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {2},
PAGES = {429-459},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/537304k2x721h132/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Green-Ives-Tannen/11,
AUTHOR = {Green, Todd J. and Ives, Zachary G. and Tannen, Val},
TITLE = {Reconcilable differences},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {2},
PAGES = {460-488},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/92j5187225755867/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Arenas-Barcelo-Reutter/11,
AUTHOR = {Arenas, Marcelo and Barcel{\'o}, Pablo and Reutter, Juan},
TITLE = {Query languages for data exchange: Beyond unions of conjunctive queries},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {2},
PAGES = {489-564},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/k40ht6648r8j2126/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Di_Giacomo-Didimo-Liotta-Meijer/11,
AUTHOR = {Di Giacomo, Emilio and Didimo, Walter and Liotta, Giuseppe and Meijer, Henk},
TITLE = {Area, curve complexity, and crossing resolution of non-planar graph drawings},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {3},
PAGES = {565-575},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/n17p7rj16l623026/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Chang-Lin-Rossmanith/11,
AUTHOR = {Chang, Maw-Shang and Lin, Chuang-Chieh and Rossmanith, Peter},
TITLE = {A property tester for tree-likeness of quartet topologies},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {3},
PAGES = {576-587},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/u50063n6p9g04uh5/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Lin-Liu-Wang-Yen/11,
AUTHOR = {Lin, Chien-Hung and Liu, Jia-Jie and Wang, Yue-Li and Yen, William Chung-Kung},
TITLE = {The hub number of Sierpi{\'n}ski-like graphs},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {3},
PAGES = {588-600},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/b78281598p765274/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Harkins-Hitchcock/11a,
AUTHOR = {Harkins, Ryan C. and Hitchcock, John M.},
TITLE = {Dimension, halfspaces, and the density of hard sets},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {3},
PAGES = {601-614},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/h411135309555003/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Bilo-Forlizzi-Proietti/11,
AUTHOR = {Bil{\`o}, Davide and Forlizzi, Luca and Proietti, Guido},
TITLE = {Approximating the metric TSP in linear time},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {3},
PAGES = {615-631},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/5g47367ku860g607/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Kawamura/11,
AUTHOR = {Kawamura, Akitoshi},
TITLE = {Generalized semimagic squares for digital halftoning},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {3},
PAGES = {632-638},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/902157676w7j0350/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Arenas-Barcelo-Libkin/11,
AUTHOR = {Arenas, Marcelo and Barcel{\'o}, Pablo and Libkin, Leonid},
TITLE = {Regular languages of nested words: Fixed points, automata, and synchronization},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {3},
PAGES = {639-670},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/x8682tx60492u146/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Floreen-Hassinen-Kaasinen-Kaski-Musto-Suomela/11,
AUTHOR = {Flor{\'e}en, Patrik and Hassinen, Marja and Kaasinen, Joel and Kaski, Petteri and Musto, Topi and Suomela, Jukka},
TITLE = {Local approximability of max-min and min-max linear programs},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {4},
PAGES = {672-697},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/vp5k7014pm375058/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Attiya-Hillel-Milani/11,
AUTHOR = {Attiya, Hagit and Hillel, Eshcar and Milani, Alessia},
TITLE = {Inherent limitations on disjoint-access parallel implementations of transactional memory},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {4},
PAGES = {698-719},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/am2730430173147p/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Nisgav-Patt-Shamir/11a,
AUTHOR = {Nisgav, Aviv and Patt-Shamir, Boaz},
TITLE = {Finding similar users in social networks},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {4},
PAGES = {720-737},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/u40nl8653t1t705q/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Azar-Feige-Gamzu-Moscibroda-Raghavendra/11,
AUTHOR = {Azar, Yossi and Feige, Uriel and Gamzu, Iftah and Moscibroda, Thomas and Raghavendra, Prasad},
TITLE = {Buffer management for colored packets with deadlines},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {4},
PAGES = {738-756},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/ej76183051g22112/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Bateni-Golab-Hajiaghayi-Karloff/11,
AUTHOR = {Bateni, MohammadHossein and Golab, Lukasz and Hajiaghayi, MohammadTaghi and Karloff, Howard},
TITLE = {Scheduling to minimize staleness and stretch in real-time data warehouses},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {4},
PAGES = {757-780},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/3656rt35q2626263/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Kuhn-Locher-Oshman/11,
AUTHOR = {Kuhn, Fabian and Locher, Thomas and Oshman, Rotem},
TITLE = {Gradient clock synchronization in dynamic networks},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {4},
PAGES = {781-816},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/k652kx643h710521/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Chan-Edmonds-Pruhs/11,
AUTHOR = {Chan, Ho-Leung and Edmonds, Jeff and Pruhs, Kirk},
TITLE = {Speed scaling of processes with arbitrary speedup curves on a multiprocessor},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {4},
PAGES = {817-833},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/1677575r40g14778/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}
@article{Racke-Rosen/11,
AUTHOR = {R{\"a}cke, Harald and Ros{\'e}n, Adi},
TITLE = {Approximation algorithms for time-constrained scheduling on line networks},
JOURNAL = {Theory of Computing Systems},
VOLUME = {49},
NUMBER = {4},
PAGES = {834-856},
YEAR = {2011},
EDITOR = {Selman, Alan L.},
URL = {http://springerlink.metapress.com/content/56u648571184up43/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
NOTE = {formerly Mathematical Systems Theory},
}