Finding edge-disjoint paths in partial k-trees

DOI10.1007/S004539910002MaRDI QIDQ1969940zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 12 December 2000

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004539910002

zbMATH Keywords

edge-coloringedge-disjoint pathspartial \(k\)-treetreewidth

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Review text

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\).

Recommendations

• Finding edge-disjoint paths in partial k-trees
• scientific article; zbMATH DE number 1303036
• Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
• Finding \(k\) partially disjoint paths in a directed planar graph
• Graph minors. XIII: The disjoint paths problem

Cited in

(19)

• Exact algorithms for finding partial edge-disjoint paths
• On structural parameterizations of the edge disjoint paths problem
• Max-multiflow/min-multicut for G+H series-parallel
• The power of cut-based parameters for computing edge-disjoint paths
• scientific article; zbMATH DE number 2086258 (Why is no real title available?)
• scientific article; zbMATH DE number 1303036 (Why is no real title available?)
• scientific article; zbMATH DE number 475595 (Why is no real title available?)
• scientific article; zbMATH DE number 1151806 (Why is no real title available?)
• Tree metrics and edge-disjoint \(S\)-paths
• Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
• Edge-disjoint paths in permutation graphs
• A tight relation between series-parallel graphs and bipartite distance hereditary graphs
• scientific article; zbMATH DE number 7278041 (Why is no real title available?)
• Walking through waypoints
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Finding edge-disjoint paths in partial k-trees
• Kernels for the disjoint paths problem on subclasses of chordal graphs
• Kernels for the disjoint paths problem on subclasses of chordal graphs
• The parameterised complexity of integer multicommodity flow

This page was built for publication: Finding edge-disjoint paths in partial \(k\)-trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1969940)