Rooted routing in the plane

DOI10.1016/0166-218X(94)00104-LzbMath0816.05050OpenAlexW1984897155MaRDI QIDQ1346696

Bruce A. 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

partitiontreesrealizationplanelinear-time algorithmhigher-genus surfacesrooted routing

Mathematics Subject Classification ID

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

Related Items

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, Combing a Linkage in an Annulus, The Induced Disjoint Paths Problem, An Improved Algorithm for Finding Cycles Through Elements, Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm, The disjoint paths problem in quadratic time, A linear time algorithm for the induced disjoint paths problem in planar graphs, Algorithms for finding an induced cycle in planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. VI. Disjoint paths across a disc
• Graph minors. VII: Disjoint paths on a surface
• Disjoint paths in graphs
• Graph minors. XIII: The disjoint paths problem
• Graph minors. II. Algorithmic aspects of tree-width
• A Polynomial Solution to the Undirected Two Paths Problem
• On the Computational Complexity of Combinatorial Problems