@incollection{Graham/09,
AUTHOR = {Graham, Ronald L.},
TITLE = {Bubblesort and juggling sequences},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1-1},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/g87538q58582gpt3/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Katoh/09,
AUTHOR = {Katoh, Naoki},
TITLE = {A proof of the molecular conjecture},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {2-3},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/422t06181106l125/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bourgeois-Croce-Escoffier-Paschos/09,
AUTHOR = {Bourgeois, N. and Croce, F. Della and Escoffier, B. and Paschos, V.Th.},
TITLE = {Exact algorithms for dominating clique problems},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {4-13},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/306h3384682275j3/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {extended abstract},
}
@incollection{Imada-Ota-Nagamochi-Akutsu/09,
AUTHOR = {Imada, Tomoki and Ota, Shunsuke and Nagamochi, Hiroshi and Akutsu, Tatsuya},
TITLE = {Enumerating stereoisomers of tree structured molecules using dynamic programming},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {14-23},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/qh76476862g20686/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bae-Choi-Lee-Tanigawa/09,
AUTHOR = {Bae, Sang Won and Choi, Sunghee and Lee, Chunseok and Tanigawa, Shin-ichi},
TITLE = {Exact algorithms for the bottleneck Steiner tree problem},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {24-33},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/j34u41v1717073pg/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {extended abstract},
}
@incollection{Hua-Yu-Lau-Wang/09,
AUTHOR = {Hua, Qiang-Sheng and Yu, Dongxiao and Lau, Francis C.M. and Wang, Yuexuan},
TITLE = {Exact algorithms for set multicover and multiset multicover problems},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {34-44},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/y7353k7r768j7356/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Claude-Dorrigiv-Durocher-Fraser-Lopez-Ortiz-Salinger/09,
AUTHOR = {Claude, Francisco and Dorrigiv, Reza and Durocher, Stephane and Fraser, Robert and L{\'o}pez-Ortiz, Alejandro and Salinger, Alejandro},
TITLE = {Practical discrete unit disk cover using an exact line-separable algorithm},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {45-54},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/d81562284605lt44/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Okumoto-Fukunaga-Nagamochi/09,
AUTHOR = {Okumoto, Kazumasa and Fukunaga, Takuro and Nagamochi, Hiroshi},
TITLE = {Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {55-64},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/r4p3h2853j4736n0/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Li-Ng/09,
AUTHOR = {Li, Shuai Cheng and Ng, Yen Kaow},
TITLE = {On protein structure alignment under distance constraint},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {65-76},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/6776358158uhh476/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bansal-Caprara-Jansen-Pradel-Sviridenko/09,
AUTHOR = {Bansal, Nikhil and Caprara, Alberto and Jansen, Klaus and Pr{\"a}del, Lars and Sviridenko, Maxim},
TITLE = {A structural lemma in 2-dimensional packing, and its implications on approximability},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {77-86},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/yg6n3230m600825r/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kavitha-Mestre/09,
AUTHOR = {Kavitha, Telikepalli and Mestre, Juli{\'a}n},
TITLE = {Max-coloring paths: Tight bounds and extensions},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {87-96},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/a741149k4q824h81/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cheung-Daescu/09,
AUTHOR = {Cheung, Yam Ki and Daescu, Ovidiu},
TITLE = {Fr{\'e}chet distance problems in weighted regions},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {97-111},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/vg996q3r2642265m/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Andersson-Miltersen/09,
AUTHOR = {Andersson, Daniel and Miltersen, Peter Bro},
TITLE = {The complexity of solving stochastic games on graphs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {112-121},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/5500m01711124283/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Iwamoto-Sasaki-Nishio-Morita/09,
AUTHOR = {Iwamoto, Chuzo and Sasaki, Kento and Nishio, Kenji and Morita, Kenichi},
TITLE = {Computational complexity of cast puzzles},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {122-131},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/d8175j6h4j8t6355/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dumitrescu-Toth/09,
AUTHOR = {Dumitrescu, Adrian and T{\'o}th, Csaba D.},
TITLE = {New bounds on the average distance from the Fermat-Weber center of a planar convex body},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {132-141},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/m2571w4172167w14/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chen-Huang-Kannan/09,
AUTHOR = {Chen, Shiteng and Huang, Zhiyi and Kannan, Sampath},
TITLE = {Reconstructing numbers from pairwise function values},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {142-152},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/e13m861h50490u07/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hansen-Lachish-Miltersen/09,
AUTHOR = {Hansen, Kristoffer Arnsfelt and Lachish, Oded and Miltersen, Peter Bro},
TITLE = {Hilbert's thirteenth problem and circuit complexity},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {153-162},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/f7275k71855134u2/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Schmidt/09,
AUTHOR = {Schmidt, Jens M.},
TITLE = {Interval stabbing problems in small integer ranges},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {163-172},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/p2876n370751k538/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Brodal-Fagerberg-Greve-Lopez-Ortiz/09,
AUTHOR = {Brodal, Gerth St{\o}lting and Fagerberg, Rolf and Greve, Mark and L{\'o}pez-Ortiz, Alejandro},
TITLE = {Online sorted range reporting},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {173-182},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/g0w76j711554w415/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Nekrich/09,
AUTHOR = {Nekrich, Yakov},
TITLE = {Data structures for approximate orthogonal range counting},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {183-192},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/82n25x9113q58566/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Brodal-Kaporis-Sioutas-Tsakalidis-Tsichlas/09,
AUTHOR = {Brodal, Gerth St{\o}lting and Kaporis, Alexis C. and Sioutas, Spyros and Tsakalidis, Konstantinos and Tsichlas, Kostas},
TITLE = {Dynamic 3-sided planar range queries with expected doubly logarithmic time},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {193-202},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/rq50m077kl227156/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Arroyuelo-Claude-Dorrigiv-Durocher-He-Lopez-Ortiz-Munro-Nicholson-Salinger-Skala/09,
AUTHOR = {Arroyuelo, Diego and Claude, Francisco and Dorrigiv, Reza and Durocher, Stephane and He, Meng and L{\'o}pez-Ortiz, Alejandro and Munro, J. Ian and Nicholson, Patrick K. and Salinger, Alejandro and Skala, Matthew},
TITLE = {Untangled monotonic chains and adaptive range search},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {203-212},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/2u81627t82361130/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kapoor-Li/09,
AUTHOR = {Kapoor, Sanjiv and Li, Xiang-Yang},
TITLE = {Geodesic spanners on polyhedral surfaces},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {213-223},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/t7x4722447200157/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chen-Wang/09a,
AUTHOR = {Chen, Danny Z. and Wang, Haitao},
TITLE = {Approximating points by a piecewise linear function: I},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {224-233},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/900873372g122178/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chen-Wang/09b,
AUTHOR = {Chen, Danny Z. and Wang, Haitao},
TITLE = {Approximating points by a piecewise linear function: II. Dealing with outliers},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {234-243},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/9784l93382015280/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Xu-Xu-Papadopoulou/09,
AUTHOR = {Xu, Jinhui and Xu, Lei and Papadopoulou, Evanthia},
TITLE = {Computing the map of geometric minimal cuts},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {244-254},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/r2635777733g8076/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fleischer-Wang/09,
AUTHOR = {Fleischer, Rudolf and Wang, Yihui},
TITLE = {On the camera placement problem},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {255-264},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/t116425x9mx38364/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fukunaga/09,
AUTHOR = {Fukunaga, Takuro},
TITLE = {Graph orientations with set connectivity requirements},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {265-274},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/bx8886810272x44j/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fomin-Gaspers-Saurabh-Thomasse/09,
AUTHOR = {Fomin, Fedor V. and Gaspers, Serge and Saurabh, Saket and Thomass{\'e}, St{\'e}phan},
TITLE = {A linear vertex kernel for {\sc Maximum Internal Spanning Tree}},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {275-282},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/u5422j6222xj1675/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Seo-Lee-Lin/09,
AUTHOR = {Seo, Dae Young and Lee, D.T. and Lin, Tien-Ching},
TITLE = {Geometric minimum diameter minimum cost spanning tree problem},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {283-292},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/v0635780642q5810/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kobayashi-Sommer/09,
AUTHOR = {Kobayashi, Yusuke and Sommer, Christian},
TITLE = {On shortest disjoint paths in planar graphs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {293-302},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/xt074674pp76w073/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hsu-Lu/09,
AUTHOR = {Hsu, Tai-Hsin and Lu, Hsueh-I},
TITLE = {An optimal labeling for node connectivity},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {303-310},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/766r222216328327/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Xu-Li/09,
AUTHOR = {Xu, Ping and Li, Xiang-Yang},
TITLE = {SOFA: Strategyproof online frequency allocation for multihop wireless networks},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {311-320},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/y8217130525hvu17/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chin-Ting-Zhang/09,
AUTHOR = {Chin, Francis Y.L. and Ting, Hing-Fung and Zhang, Yong},
TITLE = {1-bounded space algorithms for 2-dimensional bin packing},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {321-330},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/01v2n2vk335550t1/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bockenhauer-Komm-Kralovic-Kralovic-Momke/09,
AUTHOR = {B{\"o}ckenhauer, Hans-Joachim and Komm, Dennis and Kr{\'a}lovi{\v{c}}, Rastislav and Kr{\'a}lovi{\v{c}}, Richard and M{\"o}mke, Tobias},
TITLE = {On the advice complexity of online problems},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {331-340},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/q8582812k07225l1/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {extended abstrac},
}
@incollection{Han-Makino/09,
AUTHOR = {Han, Xin and Makino, Kazuhisa},
TITLE = {Online knapsack problems with limited cuts},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {341-351},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/830182444361v8q0/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kovacs-Meyer-Moruz-Negoescu/09,
AUTHOR = {Kov{\'a}cs, Annam{\'a}ria and Meyer, Ulrich and Moruz, Gabriel and Negoescu, Andrei},
TITLE = {Online paging for flash memory devices},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {352-361},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/r479p20u41692210/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Pirwani/09,
AUTHOR = {Pirwani, Imran A.},
TITLE = {Shifting strategy for geometric graphs without geometry},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {362-371},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/2u1580424537l445/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Li/09c,
AUTHOR = {Li, Minming},
TITLE = {Approximation algorithms for variable voltage processors: Min energy, max throughput and online heuristics},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {372-382},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/j7wl307qn4118x46/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Xu-Xu/09,
AUTHOR = {Xu, Zhou and Xu, Liang},
TITLE = {Approximation algorithms for min-max path cover problems with service handling time},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {383-392},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/b2750uj039653903/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Fekete-Mitchell-Schmidt/09,
AUTHOR = {Fekete, S{\'a}ndor P. and Mitchell, Joseph S.B. and Schmidt, Christiane},
TITLE = {Minimum covering with travel cost},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {393-402},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/kt04182812p63hr1/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ito-Miyamoto-Ono-Tamaki-Uehara/09,
AUTHOR = {Ito, Takehiro and Miyamoto, Yuichiro and Ono, Hirotaka and Tamaki, Hisao and Uehara, Ryuhei},
TITLE = {Route-enabling graph orientation problems},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {403-412},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/k4nh2750330n2074/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Elbassioni-Tiwary/09,
AUTHOR = {Elbassioni, Khaled and Tiwary, Hans Raj},
TITLE = {Complexity of approximating the vertex centroid of a polyhedron},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {413-422},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/d0241971r0512517/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kavitha-Nasre/09,
AUTHOR = {Kavitha, Telikepalli and Nasre, Meghana},
TITLE = {Popular matchings with variable job capacities},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {423-433},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/w6g347715h1141t2/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Zhang/09b,
AUTHOR = {Zhang, Shengyu},
TITLE = {On the tightness of the Buhrman-Cleve-Wigderson simulation},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {434-440},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/e26148280tn552t6/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Schneider-Wattenhofer/09,
AUTHOR = {Schneider, Johannes and Wattenhofer, Roger},
TITLE = {Bounds on contention management algorithms},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {441-451},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/w2663445k1557654/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cardinal-Demaine-Demaine-Imahori-Langerman-Uehara/09,
AUTHOR = {Cardinal, Jean and Demaine, Erik D. and Demaine, Martin L. and Imahori, Shinji and Langerman, Stefan and Uehara, Ryuhei},
TITLE = {Algorithmic folding complexity},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {452-461},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/x2h2574587231548/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Wu-Li-Chen/09,
AUTHOR = {Wu, Weiwei and Li, Minming and Chen, Enhong},
TITLE = {Min-energy scheduling for aligned jobs in accelerate model},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {462-472},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/p35780124165m6n6/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ishii-Makino/09,
AUTHOR = {Ishii, Toshimasa and Makino, Kazuhisa},
TITLE = {Posi-modular systems with modulotone requirements under permutation constraints},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {473-482},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/y2p05063r6785k6l/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kesh-Mehta/09,
AUTHOR = {Kesh, Deepanjan and Mehta, Shashank K.},
TITLE = {Generalized reduction to compute toric ideals},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {483-492},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/976455l234r61626/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chen-Fu/09,
AUTHOR = {Chen, Li and Fu, Bin},
TITLE = {Linear and sublinear time algorithms for basis of Abelian groups},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {493-502},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/h21v44045350225l/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Eidenbenz-Wattenhofer/09,
AUTHOR = {Eidenbenz, Raphael and Wattenhofer, Roger},
TITLE = {Good programming in transactional memory --- Game theory meets multicore architecture},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {503-513},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/n44g3685w14821r7/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Golovach-Kaminski-Paulusma-Thilikos/09,
AUTHOR = {Golovach, Petr A. and Kami{\'n}ski, Marcin and Paulusma, Dani{\"e}l and Thilikos, Dimitrios M.},
TITLE = {Induced packing of odd cycles in a planar graph},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {514-523},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/7t3p5n118t16194u/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Katoh-Tanigawa/09,
AUTHOR = {Katoh, Naoki and Tanigawa, Shin-ichi},
TITLE = {On the infinitesimal rigidity of bar-and-slider frameworks},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {524-533},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/p052317rt15g6l35/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Flocchini-Mans-Santoro/09,
AUTHOR = {Flocchini, Paola and Mans, Bernard and Santoro, Nicola},
TITLE = {Exploration of periodically varying graphs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {534-543},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/088ux352620n8444/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Guo-Niedermeier-Suchy/09,
AUTHOR = {Guo, Jiong and Niedermeier, Rolf and Such{\'y}, Ond{\v{r}}ej},
TITLE = {Parameterized complexity of arc-weighted directed Steiner problems},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {544-553},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/q71876634v655835/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Nakao-Nagamochi/09,
AUTHOR = {Nakao, Yoshitaka and Nagamochi, Hiroshi},
TITLE = {Worst case analysis for pickup and delivery problems with consecutive pickups and deliveries},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {554-563},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/177680664l67nl05/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Liu-Lu/09,
AUTHOR = {Liu, Tsung-Hao and Lu, Hsueh-I.},
TITLE = {Minimum cycle bases of weighted outerplanar graphs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {564-572},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/r6l610r66142886k/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Golovach-Heggernes-Kratsch-Lokshtanov-Meister-Saurabh/09,
AUTHOR = {Golovach, Petr and Heggernes, Pinar and Kratsch, Dieter and Lokshtanov, Daniel and Meister, Daniel and Saurabh, Saket},
TITLE = {{\sc Bandwidth} on AT-free graphs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {573-582},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/2460633288191716/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Guo-Kanj-Komusiewicz-Uhlmann/09,
AUTHOR = {Guo, Jiong and Kanj, Iyad A. and Komusiewicz, Christian and Uhlmann, Johannes},
TITLE = {Editing graphs into disjoint unions of dense clusters},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {583-593},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/t673101147741931/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bruce-Hoang-Sawada/09,
AUTHOR = {Bruce, Daniel and Ho{\`a}ng, Ch{\'{i}}nh T. and Sawada, Joe},
TITLE = {A certifying algorithm for 3-colorability of $P_5$-free graphs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {594-604},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/b47462lv22875006/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Ito-Kaminski-Paulusma-Thilikos/09,
AUTHOR = {Ito, Takehiro and Kami{\'n}ski, Marcin and Paulusma, Dani{\"e}l and Thilikos, Dimitrios M.},
TITLE = {Parameterizing cut sets in a graph by the number of their components},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {605-615},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/c648823163j3h834/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Jiang/09,
AUTHOR = {Jiang, Minghui},
TITLE = {Inapproximability of maximal strip recovery},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {616-625},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/lg36348721x6h364/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Karpinski-Rucinski-Szymanska/09,
AUTHOR = {Karpi{\'n}ski, Marek and Ruci{\'n}ski, Andrzej and Szyma{\'n}ska, Edyta},
TITLE = {The complexity of perfect matching problems on dense hypergraphs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {626-636},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/566x5030711j6406/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Arvind-Joglekar-Srinivasan/09a,
AUTHOR = {Arvind, V. and Joglekar, Pushkar S. and Srinivasan, Srikanth},
TITLE = {On lower bounds for constant width arithmetic circuits},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {637-646},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/w465q2674785x8q1/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chen-Teng/09,
AUTHOR = {Chen, Xi and Teng, Shang-Hua},
TITLE = {Spending is not easier than trading: On the computational equivalence of Fisher and Arrow-Debreu equilibria},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {647-656},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/d215m7362001x603/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bell-Potapov/09,
AUTHOR = {Bell, Paul C. and Potapov, Igor},
TITLE = {The identity correspondence problem and its applications},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {657-667},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/62515273ptm38rg8/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Czygrinow-Hanckowiak-Szymanska/09,
AUTHOR = {Czygrinow, Andrzej and Ha{\'n}{\'c}kowiak, Micha{\l} and Szyma{\'n}ska, Edyta},
TITLE = {Fast distributed approximation algorithm for the maximum matching problem in bounded arboricity graphs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {668-678},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/x01045x307241022/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Yamaguchi-Imahori-Miyashiro-Matsui/09,
AUTHOR = {Yamaguchi, Daisuke and Imahori, Shinji and Miyashiro, Ryuhei and Matsui, Tomomi},
TITLE = {An improved approximation algorithm for the traveling tournament problem},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {679-688},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/00283320712m8364/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Xu-Shen/09,
AUTHOR = {Xu, Shihong and Shen, Hong},
TITLE = {The fault-tolerant facility allocation problem},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {689-698},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/8w8hn64p74435546/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Li-Wan-Yao/09,
AUTHOR = {Li, Minming and Wan, Peng-Jun and Yao, Frances},
TITLE = {Tighter approximation bounds for minimum CDS in wireless ad hoc networks},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {699-709},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/q177601172p11771/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bulteau-Fertin-Rusu/09,
AUTHOR = {Bulteau, Laurent and Fertin, Guillaume and Rusu, Irena},
TITLE = {Maximal strip recovery problem with gaps: Hardness and approximation algorithms},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {710-719},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/15gg116027810304/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Knauer-Loffler-Scherfenberg-Wolle/09,
AUTHOR = {Knauer, Christian and L{\"o}ffler, Maarten and Scherfenberg, Marc and Wolle, Thomas},
TITLE = {The directed Hausdorff distance between imprecise point sets},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {720-729},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/h600r98541862757/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Carlsson-Singh-Zomorodian/09,
AUTHOR = {Carlsson, Gunnar and Singh, Gurjeet and Zomorodian, Afra},
TITLE = {Computing multidimensional persistence},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {730-739},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/214260815701w17l/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chen-Wang/09c,
AUTHOR = {Chen, Danny Z. and Wang, Haitao},
TITLE = {Locating an obnoxious line among planar objects},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {740-749},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/32v5487r92371412/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bonsma-Breuer/09,
AUTHOR = {Bonsma, Paul and Breuer, Felix},
TITLE = {Finding fullerene patches in polynomial time},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {750-759},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/u767220u61h2p444/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Zhou-Nishizeki/09,
AUTHOR = {Zhou, Xiao and Nishizeki, Takao},
TITLE = {Convex drawings of internally triconnected plane graphs on $O(n^2)$ grids},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {760-770},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/c771021641463217/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Jacob-Ritscher-Scheideler-Schmid/09,
AUTHOR = {Jacob, Riko and Ritscher, Stephan and Scheideler, Christian and Schmid, Stefan},
TITLE = {A self-stabilizing and local Delaunay graph construction},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {771-780},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/v280677635285682/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Goodrich-Strash/09,
AUTHOR = {Goodrich, Michael T. and Strash, Darren},
TITLE = {Succinct greedy geometric routing in the Euclidean plane},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {781-791},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/vm3x282p90768739/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kelner-Maymounkov/09,
AUTHOR = {Kelner, Jonathan and Maymounkov, Petar},
TITLE = {Electric routing and concurrent flow cutting},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {792-801},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/w6313m80q4571v04/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kamiyama-Katoh/09,
AUTHOR = {Kamiyama, Naoyuki and Katoh, Naoki},
TITLE = {A polynomial-time algorithm for the universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {802-811},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/e14t0226340543t7/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Doerr-Huber-Levavi/09,
AUTHOR = {Doerr, Benjamin and Huber, Anna and Levavi, Ariel},
TITLE = {Strong robustness of randomized rumor spreading protocols},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {812-821},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/x5172v3361nk2l58/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Brodal-Jorgensen/09,
AUTHOR = {Brodal, Gerth St{\o}lting and J{\o}rgensen, Allan Gr{\o}nlund},
TITLE = {Data structures for range median queries},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {822-831},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/yg5366j0j684l824/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Sen-Tarjan/09,
AUTHOR = {Sen, Siddhartha and Tarjan, Robert E.},
TITLE = {Deletion without rebalancing in multiway search trees},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {832-841},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/8046h882869uh605/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Brodal-Jorgensen-Moruz-Molhave/09,
AUTHOR = {Brodal, Gerth St{\o}lting and J{\o}rgensen, Allan Gr{\o}nlund and Moruz, Gabriel and M{\o}lhave, Thomas},
TITLE = {Counting in the presence of memory faults},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {842-851},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/gr27340wh49k6r04/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Schneider-Spertus/09,
AUTHOR = {Schneider, Scott and Spertus, Michael},
TITLE = {A simple, fast, and compact static dictionary},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {852-861},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/8u624x1227225075/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Biedl-Durocher-Snoeyink/09,
AUTHOR = {Biedl, Therese and Durocher, Stephane and Snoeyink, Jack},
TITLE = {Reconstructing polygons from scanner data},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {862-871},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/g61x388706123r02/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Franke-Rutter-Wagner/09,
AUTHOR = {Franke, Robert and Rutter, Ignaz and Wagner, Dorothea},
TITLE = {Computing large matchings in planar graphs with fixed minimum degree},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {872-881},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/98578jx202m8n575/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Mchedlidze-Symvonis/09b,
AUTHOR = {Mchedlidze, Tamara and Symvonis, Antonios},
TITLE = {Crossing-free acyclic Hamiltonian path completion for planar $st$-digraphs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {882-891},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/q16175815x777020/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bazgan-Couetoux-Tuza/09,
AUTHOR = {Bazgan, Cristina and Cou{\"e}toux, Basile and Tuza, Zsolt},
TITLE = {Covering a graph with a constrained forest},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {892-901},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/hj6u6014ht5657px/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {extended abstract},
}
@incollection{Al-Jubeh-Ishaque-Redei-Souvaine-Toth/09,
AUTHOR = {Al-Jubeh, Marwan and Ishaque, Mashhood and R{\'e}dei, Krist{\'o}f and Souvaine, Diane L. and T{\'o}th, Csaba D.},
TITLE = {Tri-edge-connectivity augmentation for planar straight line graphs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {902-912},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/2452g33348064738/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hong-Nagamochi/09,
AUTHOR = {Hong, Seok-Hee and Nagamochi, Hiroshi},
TITLE = {Upward star-shaped polyhedral graphs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {913-922},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/3473823576442w5q/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Tang/09,
AUTHOR = {Tang, Linqing},
TITLE = {Conditional hardness of approximating satisfiable Max 3CSP-$q$},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {923-932},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/k567w8r50411143t/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Yamakami/09,
AUTHOR = {Yamakami, Tomoyuki},
TITLE = {The roles of advice to one-tape linear-time Turing machines and finite automata},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {933-942},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/u844854721p83870/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {extended abstract},
}
@incollection{Alistarh-Gilbert-Guerraoui-Travers/09,
AUTHOR = {Alistarh, Dan and Gilbert, Seth and Guerraoui, Rachid and Travers, Corentin},
TITLE = {Of choices, failures and asynchrony: The many faces of set agreement},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {943-953},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/538551212ut24415/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Manuch-Stacho-Stoll/09,
AUTHOR = {Ma{\v{n}}uch, J{\'a}n and Stacho, Ladislav and Stoll, Christine},
TITLE = {Step-assembly with a constant number of tile types},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {954-963},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/w7633412822h40v6/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Stanley-Yang/09,
AUTHOR = {Stanley, Donald and Yang, Boting},
TITLE = {Lower bounds on fast searching},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {964-973},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/677347n853684567/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Anshelevich-Chakrabarty-Hate-Swamy/09,
AUTHOR = {Anshelevich, Elliot and Chakrabarty, Deeparnab and Hate, Ameya and Swamy, Chaitanya},
TITLE = {Approximation algorithms for the Firefighter problem: Cuts over time and submodularity},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {974-983},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/d533102v0324hm63/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Gu-Tamaki/09,
AUTHOR = {Gu, Qian-Ping and Tamaki, Hisao},
TITLE = {Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in $O(n^{1+\epsilon})$ time},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {984-993},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/51086hx03u484084/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Adamaszek-Czumaj-Lingas/09,
AUTHOR = {Adamaszek, Anna and Czumaj, Artur and Lingas, Andrzej},
TITLE = {PTAS for $k$-tour cover problem on the plane for moderately large values of $k$},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {994-1003},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/4296101w13111685/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Lin-Lee/09,
AUTHOR = {Lin, Tien-Ching and Lee, D.T.},
TITLE = {Optimal randomized algorithm for the density selection problem},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1004-1013},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/v5p4g05t07760070/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dai-Ge/09,
AUTHOR = {Dai, Decheng and Ge, Rong},
TITLE = {New results on simple stochastic games},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1014-1023},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/50x751l823x54k30/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Manthey-Roglin/09,
AUTHOR = {Manthey, Bodo and R{\"o}glin, Heiko},
TITLE = {Worst-case and smoothed analysis of $k$-means clustering with Bregman divergences},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1024-1033},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/d45q6u6pk261m343/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hon-Lam-Shah-Tam-Vitter/09,
AUTHOR = {Hon, Wing-Kai and Lam, Tak-Wah and Shah, Rahul and Tam, Siu-Lung and Vitter, Jeffrey Scott},
TITLE = {Succinct index for dynamic dictionary matching},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1034-1043},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/w50336836wjt7768/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cohen-Porat/09,
AUTHOR = {Cohen, Hagai and Porat, Ely},
TITLE = {Range non-overlapping indexing},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1044-1053},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/nv304562675815n2/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bae-Okamoto/09,
AUTHOR = {Bae, Sang Won and Okamoto, Yoshio},
TITLE = {Querying two boundary points for shortest paths in a polygonal domain},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1054-1063},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/704144443u84532p/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {extended abstract},
}
@incollection{Guillemot-Vialette/09,
AUTHOR = {Guillemot, Sylvain and Vialette, St{\'e}phane},
TITLE = {Pattern matching for 321-avoiding permutations},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1064-1073},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/52328337g548jt71/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Demaine-Demaine-Konjevod-Lang/09,
AUTHOR = {Demaine, Erik D. and Demaine, Martin L. and Konjevod, Goran and Lang, Robert J.},
TITLE = {Folding a better checkerboard},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1074-1083},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/b44687l5132366m1/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Hsu-Chen-Chao/09,
AUTHOR = {Hsu, Ping-Hui and Chen, Kuan-Yu and Chao, Kun-Mao},
TITLE = {Finding all approximate gapped palindromes},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1084-1093},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/u73151l732862m19/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Karakostas/09,
AUTHOR = {Karakostas, George},
TITLE = {General pseudo-random generators from weaker models of computation},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1094-1103},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/2r28301u20050443/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Saitoh-Otachi-Yamanaka-Uehara/09,
AUTHOR = {Saitoh, Toshiki and Otachi, Yota and Yamanaka, Katsuhisa and Uehara, Ryuhei},
TITLE = {Random generation and enumeration of bipartite permutation graphs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1104-1113},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/8380435n18530k37/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chandrasekaran-Subramani/09,
AUTHOR = {Chandrasekaran, R. and Subramani, K.},
TITLE = {A combinatorial algorithm for Horn programs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1114-1123},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/k352229k02722v72/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Bar-Noy-Lampis/09,
AUTHOR = {Bar-Noy, Amotz and Lampis, Michael},
TITLE = {Online Maximum Directed Cut},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1124-1133},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/r210u45g4x4w4202/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Cho-Mount-Park/09,
AUTHOR = {Cho, Minkyoung and Mount, David M. and Park, Eunhui},
TITLE = {Maintaining nets and net trees under incremental motion},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1134-1143},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/jn50102l66361710/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Agarwal-Narang-Shyamasundar/09,
AUTHOR = {Agarwal, Shivali and Narang, Ankur and Shyamasundar, Rudrapatna K.},
TITLE = {Distributed scheduling of parallel hybrid computations},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1144-1154},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/313h34524021mr58/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Arge-Revsbak/09,
AUTHOR = {Arge, Lars and Revsb{\ae}k, Morten},
TITLE = {I/O-efficient contour tree simplification},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1155-1165},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/b21133267m16lhmu/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Chun-Kasai-Korman-Tokuyama/09,
AUTHOR = {Chun, Jinhee and Kasai, Ryosei and Korman, Matias and Tokuyama, Takeshi},
TITLE = {Algorithms for computing the maximum weight region decomposable into elementary shapes},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1166-1174},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/q574h122141147k6/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Dillabaugh-He-Maheshwari-Zeh/09,
AUTHOR = {Dillabaugh, Craig and He, Meng and Maheshwari, Anil and Zeh, Norbert},
TITLE = {I/O and space-efficient path traversal in planar graphs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1175-1184},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/1p037328483958g1/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Kim-Choi-Na-Sim/09,
AUTHOR = {Kim, Jin Wook and Choi, Siwon and Na, Joong Chae and Sim, Jeong Seop},
TITLE = {Improved algorithms for finding consistent superstrings based on a new graph model},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1185-1194},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/9088l743607n6847/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Huang-Wei-Chen-Kao-Shih-Hsu/09,
AUTHOR = {Huang, Pei-Chi and Wei, Hsin-Wen and Chen, Yen-Chiu and Kao, Ming-Yang and Shih, Wei-Kuan and Hsu, Tsan-sheng},
TITLE = {Two-vertex connectivity augmentations for graphs with a partition constraint},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1195-1204},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/tj16tl0312083w30/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
PCOMMENT = {extended abstract},
}
@incollection{Guillemot-Jansson-Sung/09,
AUTHOR = {Guillemot, Sylvain and Jansson, Jesper and Sung, Wing-Kin},
TITLE = {Computing a smallest multi-labeled phylogenetic tree from rooted triplets},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1205-1214},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/ux3704g47u440623/fulltext.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}
@incollection{Paulusma-van_Rooij/09,
AUTHOR = {Paulusma, Dani{\"e}l and van Rooij, Johan M.M.},
TITLE = {On partitioning a graph into two connected subgraphs},
BOOKTITLE = {Proceedings of the 20th International Symposium on Algorithms and Computation, ISAAC'2009 (Honolulu, Hawaii, USA, December 16-18, 2009)},
SERIES = {LNCS},
VOLUME = {5878},
PAGES = {1215-1224},
YEAR = {2009},
EDITOR = {Dong, Yingfei and Du, Ding-Zhu and Ibarra, Oscar},
URL = {http://springerlink.metapress.com/content/u8740k7046427403/fulltext.pdf" title="Download PDF (464.9 KB)"><span>Download PDF (464.9 KB)</span></a></li> 	</ul></li><li class="primitive primitiveResource Backmatter"><p class="title">Back matter</p><ul class="resources fulltextResources" data-ftxUrl="/content/978-3-642-10630-9/#section=633260"> 		<li><a class="sprite pdf-resource-spritehttp://springerlink.metapress.com/content/978-3-642-10630-9/back-matter.pdf},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin-Heidelberg},
}