Name
Abstract | ||
|---|---|---|
Let G = (V,E) be a simple graph and s and t be two distinct vertices of G. A path in G is called l-bounded for some l ∈ N if it does not contain more than l edges. We prove that computing the maximum number of vertex-disjoint l-bounded s, t-paths is APX-complete for any l ≥ 5. This implies that the problem of finding k vertex-disjoint l-bounded s, t-paths with minimal total weight for a given number k ∈ N, 1 ≤ k ≤ |V| - 1, and nonnegative weights on the edges of G is NPO-complete for any length bound l ≥ 5. furthermore, we show that these results are tight in the sense that for l ≤ 4 both problems are polynomially solvable, assuming that the weights satisfy a generalized triangle inequality in the weighted problem. Similar results are obtained for the analogous problems with path lengths equal to l instead of at most l and with edge-disjointness instead of vertex-disjointness. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/s00037-003-0179-6 | Computational Complexity |
Keywords | Field | DocType |
k vertex-disjoint,minimal total weight,analogous problem,distinct vertex,generalized triangle inequality,number k,vertex-disjoint length-restricted path problem,most ' and with edge-disjointness instead of vertex-disjointness. keywords. disjoint paths,length restricted paths,approximability.,l edge,maximum number,weighted problem,path length,Disjoint paths,approximability,68Q25,90C27,05C38,05C40 | Graph,Discrete mathematics,Combinatorics,Disjoint sets,Vertex (geometry),Triangle inequality,Completeness (statistics),Mathematics | Journal |
Volume | Issue | ISSN |
12 | 3-4 | 1016-3328 |
Citations | PageRank | References |
20 | 1.69 | 7 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andreas Bley | 1 | 189 | 18.40 |