Back to Search
Start Over
Edge-Orienting on Split, Planar and Treelike Graphs.
- Source :
-
Computer Journal . 2007, Vol. 50 Issue 3, p357-368. 12p. - Publication Year :
- 2007
-
Abstract
- Let G(V, E) be an undirected connected graph, where each vertex v is associated with a positive cost C(v) and each edge e = (u, v) is associated with two positive weights, W(u → v) and W(v → u). We consider a new graph problem, called the edge-orientation problem (the EOP). The major issue is to assign each edge e = (u, v) an orientation, either from u to v, denoted as u → v, or from v to u, denoted as v → u, such that maxx∈V{C(x) + Σx→z W(x → z)} is minimized. This paper first shows that the EOP is NP-hard on split graphs and planar graphs. Then, a linear-time algorithm on star graphs is proposed by the prune-and-search strategy. Finally, the algorithmic result on star graphs is extended to trees and simple cactus graphs using the dynamic programming strategy. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00104620
- Volume :
- 50
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Computer Journal
- Publication Type :
- Academic Journal
- Accession number :
- 25011269
- Full Text :
- https://doi.org/10.1093/comjnl/bxl068