Finding edge-disjoint paths in partial k-trees

DOI10.1007/BFB0009496MaRDI QIDQ6487440zbMATH OpenFDO

Authors Xiao Zhou, Takao Nishizeki

Publication date 25 January 2023

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

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Finding edge-disjoint paths in partial \(k\)-trees
• scientific article; zbMATH DE number 1303036
• Edge-Coloring Partialk-Trees
• Finding \(k\) partially disjoint paths in a directed planar graph
• Graph minors. XIII: The disjoint paths problem

Cites work

• A Linear Algorithm for Edge-Coloring Series–Parallel Multigraphs
• A linear time algorithm for finding tree-decompositions of small treewidth
• Algorithms for multicommodity flows in planar graphs
• An algebraic theory of graph reduction
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Disjoint paths in a rectilinear grid
• Easy problems for tree-decomposable graphs
• Edge-Coloring Partialk-Trees
• Edge-disjoint paths in a grid bounded by two nested rectangles
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 432791 (Why is no real title available?)
• Integer plane multiflows with a mixed number of demands
• Linear-time computability of combinatorial problems on series-parallel graphs
• NP-completeness of some edge-disjoint paths problems
• On the complexity of the disjoint paths problem
• Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Practical algorithms on partial k-trees with an application to domination-like problems
• Routing through a generalized switchbox
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(7)

• Exact algorithms for finding partial edge-disjoint paths
• Finding edge-disjoint paths in partial \(k\)-trees
• scientific article; zbMATH DE number 2086258 (Why is no real title available?)
• scientific article; zbMATH DE number 1303036 (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
• The \(k\)-disjoint paths problem on chordal graphs

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 Q6487440)