Finding edge-disjoint paths in partial \(k\)-trees (Q1969940): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s004539910002 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2046202598 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 00:19, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Finding edge-disjoint paths in partial \(k\)-trees |
scientific article |
Statements
Finding edge-disjoint paths in partial \(k\)-trees (English)
0 references
12 December 2000
0 references
For a given graph \(G\) and \(p\) pairs \((s_i,t_i)\), \(1\leq i\leq p\), of vertices of \(G\), the edge-disjoint paths problem is to find \(p\) pairwise edge-disjoint paths \(P_i\), \(1\leq i \leq p\), connecting \(s_i\) and \(t_i\). This paper gives two algorithms for the edge-disjoint paths problem on partial \(k\)-trees. The first one solves the problem for any partial \(k\)-tree \(G\) and runs in polynomial time if \(p=O(\log n)\) and in linear time if \(p=O(1)\), where \(n\) is the number of vertices in \(G\). The second one solves the problem under some restrictions on the location of terminal pairs even if \(p\geq \log n\).
0 references
edge-disjoint paths
0 references
partial \(k\)-tree
0 references
treewidth
0 references
edge-coloring
0 references