@article{Hemaspaandra-Thakur/04,
AUTHOR = {Hemaspaandra, Lane A. and Thakur, Mayur},
TITLE = {Lower bounds and the hardness of counting properties},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {1-28},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {counting properties, lower bounds, rice's theorem, circuits, $UP$, $NP$, relativization, language properties},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.03.004},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Chauve-Fertin/04,
AUTHOR = {Chauve, Cedric and Fertin, Guillaume},
TITLE = {On maximal instances for the original syntenic distance},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {29-43},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {computational biology, syntenic distance, gossiping},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.05.006},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Michel/04,
AUTHOR = {Michel, Pascal},
TITLE = {Small Turing machines and generalized busy beaver competition},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {45-56},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {turing machines, decidability, busy beaver competition, $3x+1$ problem, collatz problem},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.05.008},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Eisenbrand-Grandoni/04,
AUTHOR = {Eisenbrand, Friedrich and Grandoni, Fabrizio},
TITLE = {On the complexity of fixed parameter clique and dominating set},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {57-67},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {parameterized algorithms, clique, dominating set, diamonds detection},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.05.009},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Fill-Kapur/04,
AUTHOR = {Fill, James Allen and Kapur, Nevin},
TITLE = {Limiting distributions for additive functionals on Catalan trees},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {69-102},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {catalan trees, additive functionals, limiting distributions, divide and conquer, shape functional, hadamard product of functions, singularity analysis, airy distribution, generalized polylogarithm, method of moments, central limit theorem  primary},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.05.010},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Ganjali-Hajiaghayi/04,
AUTHOR = {Ganjali, Yashar and Hajiaghayi, MohammadTaghi},
TITLE = {Characterization of networks supporting multi-dimensional linear interval routing schemes},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {103-116},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {mechanism design, connected facility location, cost sharing mechanisms, approximation algorithms},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.06.013},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Matsui-Matsui-Ono/04,
AUTHOR = {Matsui, Tomomi and Matsui, Yasuko and Ono, Yoko},
TITLE = {Random generation of $2\times 2\times \cdot \cdot \cdot \times 2\times J$ contingency tables},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {117-135},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {contingency table, markov chain monte carlo method, rapidly mixing, path coupling},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.06.014},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Bockenhauer-Bongartz-Hromkovic-Klasing-Proietti-Seibert-Unger/04,
AUTHOR = {B{\"o}ckenhauer, Hans-Joachim and Bongartz, Dirk and Hromkovi{\v{c}}, Juraj and Klasing, Ralf and Proietti, Guido and Seibert, Sebastian and Unger, Walter},
TITLE = {On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {137-153},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {approximation algorithm, inapproximability, minimum-cost biconnected spanning subgraph, graph augmentation},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.06.019},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Gonzalez-Serena/04a,
AUTHOR = {Gonzalez, Teofilo F. and Serena, David},
TITLE = {Complexity of pairwise shortest path routing in the grid},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {155-185},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {grid networks, fault-tolerance, node disjoint shortest paths, edge disjoint shortest paths, $NP$-completeness},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.06.027},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Ziegler-Brattka/04,
AUTHOR = {Ziegler, Martin and Brattka, Vasco},
TITLE = {Computability in linear algebra},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {187-211},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {computable analysis, computability, linear algebra, stability, linear equations, matrix diagonalization, spectral resolution, distance function},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.06.022},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Janson-Lonardi-Szpankowski/04a,
AUTHOR = {Janson, Svante and Lonardi, Stefano and Szpankowski, Wojciech},
TITLE = {On average sequence complexity},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {213-227},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {complexity index, sequence/subword complexity, suffix tree},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.06.023},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Duval-Kolpakov-Kucherov-Lecroq-Lefebvre/04,
AUTHOR = {Duval, Jean-Pierre and Kolpakov, Roman and Kucherov, Gregory and Lecroq, Thierry and Lefebvre, Arnaud},
TITLE = {Linear-time computation of local periods},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {229-240},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {word, period, local period, algorithm, complexity, string matching},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.06.024},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Edson-Zamboni/04,
AUTHOR = {Edson, Marcia and Zamboni, Luca Q.},
TITLE = {On representations of positive integers in the Fibonacci base},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {241-260},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {numeration systems, fibonacci numbers, generalized euclidean algorithm},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.06.025},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Fiala-Fishkin-Fomin/04,
AUTHOR = {Fiala, Ji{\v{r}}{\'{\i}} and Fishkin, Aleksei V. and Fomin, Fedor},
TITLE = {On distance constrained labeling of disk graphs},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {261-292},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {disk graph, labeling, online, approximation},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.06.026},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Jelenkovic-Radovanovic/04,
AUTHOR = {Jelenkovi{\'c}, Predrag R. and Radovanovi{\'c}, Ana},
TITLE = {Least-recently-used caching with dependent requests},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {293-327},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {least-recently-used caching, move-to-front, zipf's law, heavy-tailed distributions, long-range dependence, semi-markov processes, average-case analysis},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.07.029},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Kiwi-Russell/04,
AUTHOR = {Kiwi, Marcos and Russell, Alexander},
TITLE = {The Chilean highway problem},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {329-342},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {algorithms, packet routing, stability, scheduling protocols, server latency},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.07.030},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Dessmark-Pelc/04,
AUTHOR = {Dessmark, Anders and Pelc, Andrzej},
TITLE = {Optimal graph exploration without good maps},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {343-362},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {algorithm, exploration, graph, map, robot, traversal},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.07.031},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Yi/04a,
AUTHOR = {Yi, Xun},
TITLE = {Authenticated key agreement in dynamic peer groups},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {363-382},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {group communication, authenticated key agreement, secret-key and public-key cryptosystems, discrete logarithm problem},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.08.001},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Bernholt-Fischer/04,
AUTHOR = {Bernholt, Thorsten and Fischer, Paul},
TITLE = {The complexity of computing the MCD-estimator},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {383-398},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {computational statistics, efficient algorithms, $NP$-completeness, combinatorial geometry},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.08.005},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Li-Huang-Sun-Huang/04,
AUTHOR = {Li, Minming and Huang, Shawn L. and Sun, Xiaoming and Huang, Xiao},
TITLE = {Performance evaluation for energy efficient topologic control in ad hoc wireless networks},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {399-408},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {min power symmetric connectivity, ad hoc wireless network, approximation algorithms},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.06.017},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Gibbons-Sant/04,
AUTHOR = {Gibbons, Alan and Sant, Paul},
TITLE = {Rotation sequences and edge-colouring of binary tree pairs},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {409-418},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {graph coloring, four-colour problem, binary-tree, rotation},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.06.018},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Cheng/04a,
AUTHOR = {Cheng, Qi},
TITLE = {On the ultimate complexity of factorials},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {419-429},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {computational and structural complexity},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.06.020},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}
@article{Leonardi-Schafer/04,
AUTHOR = {Leonardi, Stefano and Sch{\"a}fer, Guido},
TITLE = {Cross-monotonic cost sharing methods for connected facility location games},
JOURNAL = {Theor.~Comput.~Sci.},
VOLUME = {326},
NUMBER = {1-3},
PAGES = {431-442},
YEAR = {2004},
EDITOR = {Ausiello, G. and Sannella, D.},
KEYWORDS = {mechanism design, connected facility location, cost sharing mechanisms, approximation algorithms},
URL = {http://dx.doi.org/10.1016/j.tcs.2004.07.033},
PUBLISHER = {Elsevier B.V.},
ADDRESS = {Amsterdam-London-New York-Oxford-Paris-Shannon-Tokyo},
}