Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Third Annual Workshop on Algorithms and Computation (WALCOM 2009)
DOI: 10.7155/jgaa.00231
Crossing-Optimal Acyclic HP-Completion for Outerplanar st-Digraphs
Vol. 15, no. 3, pp. 373-415, 2011. Regular paper.
Abstract Given an embedded planar acyclic digraph G, we define the problem
of acyclic hamiltonian path completion with crossing
minimization (acyclic-HPCCM) to be the problem of determining a
hamiltonian path completion set of edges such that, when
these edges are embedded on G, they create the smallest possible
number of edge crossings and turn G to a hamiltonian acyclic
digraph. Our results include:
|
Submitted: May 2009.
Reviewed: January 2010.
Revised: April 2010.
Accepted: October 2010.
Final: November 2010.
Published: July 2011.
|
Journal Supporters
|