Name
Abstract | ||
|---|---|---|
st-orientations (st-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 st-orientation of a biconnected graph. In this paper, we present new algorithms that compute such orientations with certain (parameterized) characteristics in the final st-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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.tcs.2008.08.012 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
final solution,s t -numberings,undirected graph,final st-oriented graph,longest path,Graph algorithms,graph algorithm,graph coloring,Planar graphs,course longest path,certain feature,Longest path,biconnected graph,parameterized st-orientation,Graph Drawing | Journal | 408 |
Issue | ISSN | Citations |
2-3 | Theoretical Computer Science | 8 |
PageRank | References | Authors |
0.51 | 15 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Charalampos Papamanthou | 1 | 1109 | 54.41 |
| Ioannis G. Tollis | 2 | 1240 | 162.75 |