Rooted routing in the plane

DOI10.1016/0166-218X(94)00104-LMaRDI QIDQ1346696zbMATH OpenOpenAlexFDO

Authors Bruce Reed

Publication date 10 April 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(94)00104-l

zbMATH Keywords

higher-genus surfaceslinear-time algorithmpartitionplanerealizationrooted routingtrees

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

A partition \(P= \{P_ 1,\dots, P_ p\}\) of a set \(X\) of vertices of a graph \(G\) is realizable if there are vertex-disjoint trees \(T_ 1,\dots, T_ p\) in \(G\) such that \(P_ i\subseteq V(T_ i)\), for \(1\leq i\leq p\). A realization of \(P\) is such a set of trees. In this paper the author discusses a linear-time algorithm for instances of \(k\)-realizations (Input: a graph \(G\) and a set \(X\subseteq V(G)\) with \(| X|= k\). Question: which partitions of \(X\) are realizable in \(G\)?) where \(G\) is planar. The algorithm is due to \textit{B. A. Reed}, \textit{N. Robertson}, \textit{A. Schrijver} and \textit{P. D. Seymour} [Contemp. Math. 147, 295-301 (1993; Zbl 0791.05092)]. Also considered in the present paper are extensions to higher-genus surfaces and an algorithm of Robertson and Seymour for \(k\)-realizations in arbitrary graphs.

Recommendations

• scientific article; zbMATH DE number 508832
• Disjoint homotopic paths and trees in a planar graph
• scientific article; zbMATH DE number 4108779
• Partitions of Graphs into Trees
• scientific article; zbMATH DE number 1262808

Cites work

• A Polynomial Solution to the Undirected Two Paths Problem
• Disjoint paths in graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. VI. Disjoint paths across a disc
• Graph minors. VII: Disjoint paths on a surface
• Graph minors. XIII: The disjoint paths problem
• Graph theory
• scientific article; zbMATH DE number 3588683 (Why is no real title available?)
• scientific article; zbMATH DE number 475595 (Why is no real title available?)
• On the Computational Complexity of Combinatorial Problems

Cited in

(16)

• Linear time algorithms for two disjoint paths problems on directed acyclic graphs
• The Induced Disjoint Paths Problem
• An Improved Algorithm for Finding Cycles Through Elements
• The disjoint paths problem in quadratic time
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• scientific article; zbMATH DE number 508832 (Why is no real title available?)
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• Combing a Linkage in an Annulus
• Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm
• Algorithms for finding an induced cycle in planar graphs
• Kernels for the disjoint paths problem on subclasses of chordal graphs
• Kernels for the disjoint paths problem on subclasses of chordal graphs
• A rooted-forest partition with uniform vertex demand
• Rerouting planar curves and disjoint paths
• Constant approximating disjoint paths on acyclic digraphs is W[1]-hard
• (Almost-)optimal FPT algorithm and kernel for T-cycle on planar graphs

This page was built for publication: Rooted routing in the plane

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