Journal of Graph Algorithms and Applications

http://jgaa.info ISSN: 1526-1719

Volume 10, 2006

Volume 10, no. 1, 2006
Special Issue on Selected Papers from the Engineering and Applications Track of the 12th Annual European Symposium on Algorithms (ESA 2004)

• Guest Editor's Foreword
  Tomasz Radzik
  Vol. 10, no. 1, pp. 3-4, 2006.
  • article (PDF)
• Contraction and Treewidth Lower Bounds
  Hans L. Bodlaender, Thomas Wolle and Arie M. C. A. Koster
  Vol. 10, no. 1, pp. 5-49, 2006. Regular paper.
  Submitted: August 2004. Revised: July 2005.
  Communicated by Tomasz Radzik.
  
  • article (PDF)
• Distributing Unit Size Workload Packages in Heterogeneous Networks
  Robert Elsässer, Burkhard Monien and Stefan Schamberger
  Vol. 10, no. 1, pp. 51-68, 2006. Regular paper.
  Submitted: Semptember 2004. Revised: April 2005.
  Communicated by Tomasz Radzik.
  
  • article (PDF)
• Finding Dominators in Practice
  Loukas Georgiadis, Robert E. Tarjan and Renato F. Werneck
  Vol. 10, no. 1, pp. 69-94, 2006. Regular paper.
  Submitted: September 2004. Revised: September 2005.
  Communicated by Tomasz Radzik.
  
  • article (PDF)

Volume 10, no. 2, 2006

• Collective Tree Spanners and Routing in AT-free Related Graphs
  Feodor F. Dragan, Chenyu Yan and Derek G. Corneil
  Vol. 10, no. 2, pp. 97-122, 2006. Regular paper.
  Submitted: January 2005. Revised: January 2006.
  Communicated by Samir Khuller.
  
  • article (PDF)
• A Factor-Two Approximation Algorithm for Two-Dimensional Phase Unwrapping
  Reuven Bar-Yehuda and Irad Yavneh
  Vol. 10, no. 2, pp. 123-139, 2006. Regular paper.
  Submitted: October 2004. Revised: November 2005.
  Communicated by Martin Fürer.
  
  • article (PDF)
• Orthogonal Hypergraph Drawing for Improved Visibility
  Thomas Eschbach, Wolfgang Guenther and Bernd Becker
  Vol. 10, no. 2, pp. 141-157, 2006. Regular paper.
  Submitted: April 2004. Revised: November 2005.
  Communicated by and Giuseppe Liotta.
  
  • article (PDF)
• A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs
  Grant A. Cheston and Tjoen Seng Jap
  Vol. 10, no. 2, pp. 159-190, 2006. Survey paper.
  Submitted: May 2005. Revised: April 2006.
  Communicated by Alan Gibbons.
  
  • article (PDF)
• Computing Communities in Large Networks Using Random Walks
  Pascal Pons and Matthieu Latapy
  Vol. 10, no. 2, pp. 191-218, 2006. Regular paper.
  Submitted: November 2005. Revised: April 2006.
  Communicated by Ulrik Brandes.
  
  • article (PDF)
• Algorithms and Experiments for the Webgraph
  Debora Donato, Luigi Laura, Stefano Leonardi, Ulrich Meyer, Stefano Millozzi and Jop F. Sibeyn
  Vol. 10, no. 2, pp. 219-236, 2006. Regular paper.
  Submitted: February 2005. Revised: February 2006.
  Communicated by Dorothea Wagner.
  
  • article (PDF)
• A Multilevel Algorithm for the Minimum 2-sum Problem
  Ilya Safro, Dorit Ron and Achi Brandt
  Vol. 10, no. 2, pp. 237-258, 2006. Regular paper.
  Submitted: October 2004. Revised: March 2006.
  Communicated by Ernst W. Mayr.
  
  • article (PDF)
• Upward Planar Drawings and Switch-regularity Heuristics
  Walter Didimo
  Vol. 10, no. 2, pp. 259-285, 2006. Regular paper.
  Submitted: March 2005. Revised: March 2006.
  Communicated by Michael Kaufmann.
  
  • article (PDF)
• Drawing Kn in Three Dimensions with One Bend per Edge
  Olivier Devillers, Hazel Everett, Sylvain Lazard, Maria Pentcheva and Stephen Wismath
  Vol. 10, no. 2, pp. 287-295, 2006. Concise paper.
  Submitted: September 2005. Revised: March 2006.
  Communicated by Henk Meijer.
  
  • article (PDF)
• On the approximation of Min Split-coloring and Min Cocoloring
  Marc Demange, Tinaz Ekim and Dominique de Werra
  Vol. 10, no. 2, pp. 297-315, 2006. Regular paper.
  Submitted: June 2005. Revised: April 2006.
  Communicated by Martin Fürer.
  
  • article (PDF)
• NP-completeness of the Planar Separator Problems
  Junichiro Fukuyama
  Vol. 10, no. 2, pp. 317-328, 2006. Regular paper.
  Submitted: November 2001. Revised: October 2005.
  Communicated by Martin Fürer.
  
  • article (PDF)
• Efficient drawing of RNA secondary structure
  David Auber, Maylis Delest, Jean-Philippe Domenger and Serge Dulucq
  Vol. 10, no. 2, pp. 329-351, 2006. Regular paper.
  Submitted: March 2005. Revised: June 2006.
  Communicated by Michael T. Goodrich.
  
  • article (PDF)
• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
  Sergio Cabello
  Vol. 10, no. 2, pp. 353-363, 2006. Regular paper.
  Submitted: July 2005. Revised: June 2006.
  Communicated by Michael T. Goodrich.
  
  • article (PDF)
• Small Stretch Spanners on Dynamic Graphs
  Giorgio Ausiello, Paolo G. Franciosa and Giuseppe F. Italiano
  Vol. 10, no. 2, pp. 365-385, 2006. Regular paper.
  Submitted: November 2005. Revised: June 2006.
  Communicated by Giuseppe Liotta.
  
  • article (PDF)
• A New Algorithm for Finding Minimal Cycle-Breaking Sets of Turns in a Graph
  Lev Levitin, Mark Karpovsky, Mehmet Mustafa and Lev Zakrevski
  Vol. 10, no. 2, pp. 387-420, 2006. Regular paper.
  Submitted: July 2005. Revised: April 2006.
  Communicated by Samir Khuller.
  
  • article (PDF)