Finding edge-disjoint paths in partial k-trees

DOI10.1007/BFB0009496zbMath1512.68256MaRDI QIDQ6487440

Xiao Zhou, Takao Nishizeki, Unnamed Author

Publication date: 25 January 2023

Mathematics Subject Classification ID

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

Cites Work

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

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