Finding Edge-Disjoint Paths in Partial k -Trees

No abstract is available for this paper.

• Publication year

  2000

• Venue

  Algorithmica

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s004539910002
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Edge-Disjoint Paths Problem is NP-Complete for Partial k-Trees

  1998cited by this paper
• Edge-Coloring Partial k-Trees

  1996cited by this paper
• A Linear Algorithm for Edge-Coloring Series-Parallel Multigraphs

  1996cited by this paper
• Graph Minors .XIII. The Disjoint Paths Problem

  1995cited by this paper
• NP-completeness of Some Edge-disjoint Paths Problems

  1995cited by this paper
• Optimal parallel algorithm for edge-coloring partial k-trees with bounded degrees

  1994cited by this paper
• A linear time algorithm for finding tree-decompositions of small treewidth

  1993cited by this paper
• A linear-time algorithm for edge-disjoint paths in planar graphs

  1993cited by this paper
• Integer Plane Multiflows with a Fixed Number of Demands

  1993cited by this paper
• Practical Algorithms on Partial k-Trees with an Application to Domination-like Problems

  1993cited by this paper
• On the complexity of the disjoint paths problem

  1993cited by this paper
• Easy Problems for Tree-Decomposable Graphs

  1991cited by this paper
• An algebraic theory of graph reduction

  1990cited by this paper
• Finding Steiner forests in planar graphs

  1990cited by this paper
• Polynomial algorithms for graph isomorphism and chromatic index on partial k -trees

  1990influential reference
• The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs

  1990cited by this paper
• Edge-disjoint paths in a grid bounded by two nested rectangles

  1990cited by this paper
• Polynomial Algorithms for Graph Isomorphism and Chromatic Index on Partial k-Trees

  1988cited by this paper
• Planar Multicommodity Flows, Maximum Matchings and Negative Cycles

  1986cited by this paper
• Graph Minors. II. Algorithmic Aspects of Tree-Width

  1986cited by this paper
• Routing through a rectangle

  1986cited by this paper
• Routing Through a Generalized Switchbox

  1985cited by this paper
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks

  1985cited by this paper
• A Linear-Time Routing Algorithm for Convex Grids

  1985cited by this paper
• Linear-time computability of combinatorial problems on series-parallel graphs

  1982cited by this paper
• private communication

  1969cited by this paper

• Structural Parameterization of Steiner Tree Packing

  2025cites this paper
• The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs

  2025cites this paper
• Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures

  2024cites this paper
• Kernels for the Disjoint Paths Problem on Subclasses of Chordal Graphs

  2023cites this paper
• The Parameterised Complexity of Integer Multicommodity Flow

  2023cites this paper
• The Power of Cut-Based Parameters for Computing Edge-Disjoint Paths

  2018cites this paper
• Waypoint Routing in Special Networks

  2018cites this paper
• Walking Through Waypoints

  2017cites this paper
• Charting the Complexity Landscape of Waypoint Routing

  2017cites this paper
• On Structural Parameterizations of the Edge Disjoint Paths Problem

  2017cites this paper
• A tight relation between series-parallel graphs and Bipartite Distance Hereditary graphs

  2015cites this paper
• Finding Paths with Minimum Shared Edges in Graphs with Bounded Treewidth

  2013cites this paper
• A Generalized Network Model for Freight Car Distribution

  2011cites this paper
• Max-multiflow/min-multicut for G+H series-parallel

  2011cites this paper
• Approximation Algorithms for Edge-Disjoint Paths and Unsplittable Flow

  2006cites this paper
• Arc-disjoint paths in expander digraphs

  2001cites this paper
• The edge-disjoint paths problem is NP-complete for series-parallel graphs

  2001cites this paper
• Finding Independent Spanning Trees in Partial k-Trees

  2000cites this paper
• Generalized Vertex-Colorings of Partial K-Trees

  2000cites this paper
• The Edge-Disjoint Paths Problem is NP-Complete for Partial k-Trees

  1998cites this paper
• A Polynomial-Time Algorithm for Finding Total Colorings of Partial k-Trees

  1998cites this paper
• Critical Resource Sharing for Cooperation in Complex Systems Deliverable D3.1 Scheduling in Modern Networks: State-of-the-art Survey

  year unknowncites this paper