Rooted routing in the plane (Q1346696): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Bruce A. Reed / rank | |||
Property / reviewed by | |||
Property / reviewed by: Arthur T. White / rank | |||
Property / author | |||
Property / author: Bruce A. Reed / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Arthur T. White / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5422499 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Computational Complexity of Combinatorial Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4273851 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph minors. II. Algorithmic aspects of tree-width / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph minors. VI. Disjoint paths across a disc / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph minors. XIII: The disjoint paths problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Graph minors. VII: Disjoint paths on a surface / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Disjoint paths in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Polynomial Solution to the Undirected Two Paths Problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4156452 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0166-218x(94)00104-l / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1984897155 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 11:38, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Rooted routing in the plane |
scientific article |
Statements
Rooted routing in the plane (English)
0 references
10 April 1995
0 references
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.
0 references
rooted routing
0 references
plane
0 references
partition
0 references
trees
0 references
realization
0 references
linear-time algorithm
0 references
higher-genus surfaces
0 references