Algorithms for computing a parameterized st-orientation

TitleAlgorithms for computing a parameterized st-orientation
Publication TypeJournal Articles
Year of Publication2008
AuthorsPapamanthou C, Tollis IG
JournalTheoretical Computer Science
Pagination224 - 240
Date Published2008/11/28/
ISBN Number0304-3975
KeywordsGraph algorithms, Longest path, Planar graphs, s t -numberings

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.

Short TitleTheoretical Computer Science