TY - JOUR
T1 - Algorithms for computing a parameterized st-orientation
JF - Theoretical Computer Science
Y1 - 2008
A1 - Charalampos Papamanthou
A1 - Tollis, Ioannis G.
KW - Graph algorithms
KW - Longest path
KW - Planar graphs
KW - s t -numberings
AB - s t -orientations ( s t -numberings) or bipolar orientations of undirected graphs are central to many graph algorithms and applications. Several algorithms have been proposed in the past to compute an s t -orientation of a biconnected graph. In this paper, we present new algorithms that compute such orientations with certain (parameterized) characteristics in the final s t -oriented graph, such as the length of the longest path. This work has many applications, including Graph Drawing and Network Routing, where the length of the longest path is vital in deciding certain features of the final solution. This work applies to other difficult problems as well, such as graph coloring and of course longest path. We present extended theoretical and experimental results which show that our technique is efficient and performs well in practice.
VL - 408
SN - 0304-3975
UR - http://www.sciencedirect.com/science/article/pii/S0304397508005653
CP - 2–3
J1 - Theoretical Computer Science
ER -