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

treespartitionrealizationlinear-time algorithmplanehigher-genus surfacesrooted routing

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3588683 (Why is no real title available?)
• scientific article; zbMATH DE number 475595 (Why is no real title available?)
• 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
• On the Computational Complexity of Combinatorial Problems

Cited in

(10)

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

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)