@article{Pisinger/99, AUTHOR = {Pisinger, David}, TITLE = {Linear time algorithms for Knapsack Problems with bounded weights}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {1}, PAGES = {1-14}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Cheriyan-Thurimella/99, AUTHOR = {Cheriyan, Joseph and Thurimella, Ramakrishna}, TITLE = {Fast algorithms for $k$-shredders and $k$-node connectivity augmentation}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {1}, PAGES = {15-50}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Fleischer/99a, AUTHOR = {Fleischer, Lisa}, TITLE = {Building chain and cactus representations of all minimum cuts from Hao-Orlin in the same asymptotic run time}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {1}, PAGES = {51-72}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Charikar-Chekuri-Cheung-Dai-Goel-Guha-Li/99, AUTHOR = {Charikar, Moses and Chekuri, Chandra and Cheung, To-yat and Dai, Zuo and Goel, Ashish and Guha, Sudipto and Li, Ming}, TITLE = {Approximation algorithms for directed Steiner problems}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {1}, PAGES = {73-91}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Krumke-Marathe-Noltemeier-Ravi-Ravi-Sundaram-Wirth/99, AUTHOR = {Krumke, S.O. and Marathe, M.V. and Noltemeier, H. and Ravi, R. and Ravi, S.S. and Sundaram, S. and Wirth, H.-C.}, TITLE = {Improving minimum cost spanning trees by upgrading nodes}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {1}, PAGES = {92-111}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Subramanian/99, AUTHOR = {Subramanian, C.R.}, TITLE = {Minimum coloring $k$-coloring graphs in polynomial average time}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {1}, PAGES = {112-123}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Yeo/99a, AUTHOR = {Yeo, Anders}, TITLE = {A polynomial time algorithm for finding a cycle covering a given set of vertices in a semicomplete multipartite graph}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {1}, PAGES = {124-139}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Lopez-Reisner/99, AUTHOR = {Lopez, Mario A. and Reisner, Shlomo}, TITLE = {Algorithms for polyhedral approximation of multidimensional ellipsoids}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {1}, PAGES = {140-165}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Frieze-Molloy/99, AUTHOR = {Frieze, Alan M. and Molloy, Michael}, TITLE = {Splitting an expander graph}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {1}, PAGES = {166-172}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Alon-Sudakov/99, AUTHOR = {Alon, Noga and Sudakov, Benny}, TITLE = {On two segmentation problems}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {1}, PAGES = {173-184}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Pritchard/99a, AUTHOR = {Pritchard, Paul}, TITLE = {On computing the subset graph of a collection of sets}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {2}, PAGES = {187-203}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Huang-Rao/99, AUTHOR = {Huang, Ming-Deh A. and Rao, Ashwin J.}, TITLE = {Interpolation of sparse multivariate polynomials over large finite fields with applications}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {2}, PAGES = {204-228}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Thorup/99a, AUTHOR = {Thorup, Mikkel}, TITLE = {Decremental dynamic connectivity}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {2}, PAGES = {229-243}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Frederickson-Solis-Oba/99, AUTHOR = {Frederickson, Greg N. and Solis-Oba, Roberto}, TITLE = {Increasing the weight of minimum spanning trees}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {2}, PAGES = {244-266}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Shamir-Tsur/99, AUTHOR = {Shamir, Ron and Tsur, Dekel}, TITLE = {Faster subtree isomorphism}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {2}, PAGES = {267-280}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Panaite-Pelc/99, AUTHOR = {Panaite, Petri{\c{s}}or and Pelc, Andrzej}, TITLE = {Exploring unknown undirected graphs}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {2}, PAGES = {281-295}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Bertsimas-Gamarnik/99, AUTHOR = {Bertsimas, Dimitris and Gamarnik, David}, TITLE = {Asymptotically optimal algorithms for job shop scheduling and packet routing}, JOURNAL = {J. Algorithms}, VOLUME = {33}, NUMBER = {2}, PAGES = {296-318}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Bshouty/99, AUTHOR = {Bshouty, Nader H.}, TITLE = {Lower bounds for the complexity of functions in a realistic RAM model}, JOURNAL = {J. Algorithms}, VOLUME = {32}, NUMBER = {1}, PAGES = {1-20}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Auletta-Dinitz-Nutov-Parente/99, AUTHOR = {Auletta, Vincenzo and Dinitz, Yefim and Nutov, Zeev and Parente, Domenico}, TITLE = {A 2-approximation algorithm for finding an optimum 3-vertex-connected spanning subgraph}, JOURNAL = {J. Algorithms}, VOLUME = {32}, NUMBER = {1}, PAGES = {21-30}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Dinitz-Nutov/99, AUTHOR = {Dinitz, Yefim and Nutov, Zeev}, TITLE = {A 3-approximation algorithm for finding optimum 4,5-vertex-connected spanning subgraphs}, JOURNAL = {J. Algorithms}, VOLUME = {32}, NUMBER = {1}, PAGES = {31-40}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Kloks-Kratsch-Muller/99, AUTHOR = {Kloks, Ton and Kratsch, Dieter and M{\"u}ller, Haiko}, TITLE = {Approximating the bandwidth for asteroidal triple-free graphs}, JOURNAL = {J. Algorithms}, VOLUME = {32}, NUMBER = {1}, PAGES = {41-57}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Gobel-Walter/99, AUTHOR = {G{\"o}bel, Manfred and Walter, Jochen}, TITLE = {Bases for polynomial invariants of conjugates of permutation groups}, JOURNAL = {J. Algorithms}, VOLUME = {32}, NUMBER = {1}, PAGES = {58-61}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Bonizzoni-Della_Vedova/99, AUTHOR = {Bonizzoni, Paola and Della Vedova, Gianluca}, TITLE = {An algorithm for the modular decomposition of hypergraphs}, JOURNAL = {J. Algorithms}, VOLUME = {32}, NUMBER = {2}, PAGES = {65-86}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Provan-Burk/99, AUTHOR = {Provan, J. Scott and Burk, Roger C.}, TITLE = {Two-connected augmentation problems in planar graphs}, JOURNAL = {J. Algorithms}, VOLUME = {32}, NUMBER = {2}, PAGES = {87-107}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Gil-Itai/99, AUTHOR = {Gil, Joseph and Itai, Alon}, TITLE = {How to pack trees}, JOURNAL = {J. Algorithms}, VOLUME = {32}, NUMBER = {2}, PAGES = {108-132}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Klarlund/99, AUTHOR = {Klarlund, Nils}, TITLE = {An $n \log n$ algorithm for online BDD refinement}, JOURNAL = {J. Algorithms}, VOLUME = {32}, NUMBER = {2}, PAGES = {133-154}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Li-Zhang/99, AUTHOR = {Li, Ming and Zhang, Louxin}, TITLE = {Twist-rotation transformations of binary trees and arithmetic expressions}, JOURNAL = {J. Algorithms}, VOLUME = {32}, NUMBER = {2}, PAGES = {155-166}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Bodlaender-Thilikos/99, AUTHOR = {Bodlaender, Hans L. and Thilikos, Dimitrios M.}, TITLE = {Graphs with branchwidth at most three}, JOURNAL = {J. Algorithms}, VOLUME = {32}, NUMBER = {2}, PAGES = {167-194}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Milidiu-Laber-Pessoa/99, AUTHOR = {Milidi{\'u}, Ruy Luiz and Laber, Eduardo Sany and Pessoa, Artur Alves}, TITLE = {Bounding the compression loss of the FGK algorithm}, JOURNAL = {J. Algorithms}, VOLUME = {32}, NUMBER = {2}, PAGES = {195-211}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Basch-Guibas-Hershberger/99, AUTHOR = {Basch, Julien and Guibas, Leonidas J. and Hershberger, John}, TITLE = {Data structures for mobile data}, JOURNAL = {J. Algorithms}, VOLUME = {31}, NUMBER = {1}, PAGES = {1-28}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Miller-Talmor-Teng/99, AUTHOR = {Miller, Gary L. and Talmor, Dafna and Teng, Shang-Hua}, TITLE = {Optimal coarsening of unstructured meshes}, JOURNAL = {J. Algorithms}, VOLUME = {31}, NUMBER = {1}, PAGES = {29-65}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{LaMarca-Ladner/99, AUTHOR = {LaMarca, Anthony and Ladner, Richard E.}, TITLE = {The influence of caches on the performance of sorting}, JOURNAL = {J. Algorithms}, VOLUME = {31}, NUMBER = {1}, PAGES = {66-104}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Meyer_auf_der_Heide-Vocking/99, AUTHOR = {Meyer auf der Heide, Friedhelm and V{\"o}cking, Berthold}, TITLE = {Shortest-path routing in arbitrary networks}, JOURNAL = {J. Algorithms}, VOLUME = {31}, NUMBER = {1}, PAGES = {105-131}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Kantor-Luks-Mark/99, AUTHOR = {Kantor, William M. and Luks, Eugene M. and Mark, Peter D.}, TITLE = {Sylow subgroups in parallel}, JOURNAL = {J. Algorithms}, VOLUME = {31}, NUMBER = {1}, PAGES = {132-195}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Faigle-Kern-Nawijn/99, AUTHOR = {Faigle, U. and Kern, W. and Nawijn, W.M.}, TITLE = {A greedy on-line algorithm for the $k$-track assignment problem}, JOURNAL = {J. Algorithms}, VOLUME = {31}, NUMBER = {1}, PAGES = {196-210}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Fujito/99, AUTHOR = {Fujito, Toshihiro}, TITLE = {Approximating node-deletion problems for matroidal properties}, JOURNAL = {J. Algorithms}, VOLUME = {31}, NUMBER = {1}, PAGES = {211-227}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Guha-Khuller/99a, AUTHOR = {Guha, Sudipto and Khuller, Samir}, TITLE = {Greedy strikes back: Improved facility location algorithms}, JOURNAL = {J. Algorithms}, VOLUME = {31}, NUMBER = {1}, PAGES = {228-248}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Bazgan-Santha-Tuza/99, AUTHOR = {Bazgan, Cristina and Santha, Miklos and Tuza, Zsolt}, TITLE = {On the approximation of finding a(nother) Hamiltonian cycle in cubic Hamiltonian graphs}, JOURNAL = {J. Algorithms}, VOLUME = {31}, NUMBER = {1}, PAGES = {249-268}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Bender-Canfield/99, AUTHOR = {Bender, Edward A. and Canfield, E. Rodney}, TITLE = {An approximate probabilistic model for structured Gaussian elimination}, JOURNAL = {J. Algorithms}, VOLUME = {31}, NUMBER = {2}, PAGES = {271-290}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Ferragina-Grossi/99a, AUTHOR = {Ferragina, Paolo and Grossi, Roberto}, TITLE = {Improved dynamic text indexing}, JOURNAL = {J. Algorithms}, VOLUME = {31}, NUMBER = {2}, PAGES = {291-319}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Saks-Zaharoglou/99, AUTHOR = {Saks, Michael and Zaharoglou, Fotios}, TITLE = {Optimal space distributed order-preserving lists}, JOURNAL = {J. Algorithms}, VOLUME = {31}, NUMBER = {2}, PAGES = {320-334}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Mahajan-Raman/99, AUTHOR = {Mahajan, Meena and Raman, Venkatesh}, TITLE = {Parameterizing above guaranteed values: MaxSat and MaxCut}, JOURNAL = {J. Algorithms}, VOLUME = {31}, NUMBER = {2}, PAGES = {335-354}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Andersson/99, AUTHOR = {Andersson, Arne}, TITLE = {General balanced trees}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {1}, PAGES = {1-18}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Shi-Spencer/99, AUTHOR = {Shi, Hanmao and Spencer, Thomas H.}, TITLE = {Time-work tradeoffs of the single-source shortest paths problem}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {1}, PAGES = {19-32}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Dietz-Raman/99, AUTHOR = {Dietz, Paul F. and Raman, Rajeev}, TITLE = {Small-rank selection in parallel, with applications to heap construction}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {1}, PAGES = {33-51}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Teng/99, AUTHOR = {Teng, Shang-Hua}, TITLE = {Low energy and mutually distant sampling}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {1}, PAGES = {52-67}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Afek-Weisberger/99, AUTHOR = {Afek, Yehuda and Weisberger, Eytan}, TITLE = {The instancy of snapshots and commuting objects}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {1}, PAGES = {68-105}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Afek-Mansour-Ostfeld/99, AUTHOR = {Afek, Yehuda and Mansour, Yishay and Ostfeld, Zvi}, TITLE = {Convergence complexity of optimistic rate-based flow-control algorithms}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {1}, PAGES = {106-143}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Kutten-Peleg/99, AUTHOR = {Kutten, Shay and Peleg, David}, TITLE = {Fault-local distributed mending}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {1}, PAGES = {144-165}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Brandstadt-Chepoi-Dragan/99, AUTHOR = {Brandst{\"a}dt, Andreas and Chepoi, Victor and Dragan, Feodor}, TITLE = {Distance approximating trees for chordal and dually chordal graphs}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {1}, PAGES = {166-184}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Yanez-Montero/99, AUTHOR = {Y{\'{a}}{\~{n}}ez, Javier and Montero, Javier}, TITLE = {A poset dimension algorithm}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {1}, PAGES = {185-208}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Cohen-Lewis/99, AUTHOR = {Cohen, Edith and Lewis, David D.}, TITLE = {Approximating matrix multiplication for pattern recognition tasks}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {2}, PAGES = {211-252}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Nagamochi-Ibaraki/99, AUTHOR = {Nagamochi, Hiroshi and Ibaraki, Toshihide}, TITLE = {Augmenting edge-connectivity over the entire range in $\tilde{O}(nm)$ time}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {2}, PAGES = {253-301}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Amenta-Bern-Eppstein/99, AUTHOR = {Amenta, Nina and Bern, Marshall and Eppstein, David}, TITLE = {Optimal point placement for mesh smoothing}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {2}, PAGES = {302-322}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Chudak-Shmoys/99, AUTHOR = {Chudak, Fabi{\'{a}}n A. and Shmoys, David B.}, TITLE = {Approximation algorithm for precedence-constrained scheduling problems on parallel machines that run at different speeds}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {2}, PAGES = {323-343}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Booth-Govindan-Langston-Ramachandramurthi/99, AUTHOR = {Booth, Heather D. and Govindan, Rajeev and Langston, Michael A. and Ramachandramurthi, Siddharthan}, TITLE = {Fast algorithms for $K_4$ immersion testing}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {2}, PAGES = {344-378}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Dolev-Kranakis-Krizanc/99, AUTHOR = {Dolev, Shlomi and Kranakis, Evangelos and Krizanc, Danny}, TITLE = {Baked-potato routing}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {2}, PAGES = {379-399}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Lustig-Shmueli/99, AUTHOR = {Lustig, Aviv and Shmueli, Oded}, TITLE = {Acyclic hypergraph projections}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {2}, PAGES = {400-422}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Chen-Hwang-Chen/99, AUTHOR = {Chen, Wei-Mei and Hwang, Hsien-Kuei and Chen, Gen-Huey}, TITLE = {The cost distribution of queue-mergesort, optimal mergesorts, and power-of-2 rules}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {2}, PAGES = {423-448}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, } @article{Khuller-Agarwal-ORourke/99, AUTHOR = {Khuller, Samir and Agarwal, Pankaj K. and O'Rourke, Joseph}, TITLE = {Problems --- Open problems presented at SCG'98}, JOURNAL = {J. Algorithms}, VOLUME = {30}, NUMBER = {2}, PAGES = {449-453}, YEAR = {1999}, PUBLISHER = {Academic Press}, ADDRESS = {San Diego-London}, }