On Interval Routing Schemes and treewidth

DOI10.1007/3-540-60618-1_75MaRDI QIDQ6122222zbMATH OpenOpenAlexFDO

Authors Hans L. Bodlaender, Dimitrios M. Thilikos, J. Van Leeuwen

Publication date 28 February 2024

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/18307

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On interval routing schemes and treewidth
• Interval Routing onk-Trees
• Quickly excluding \(K_{2,r}\) from planar graphs
• Partial characterizations of networks supporting shortest path interval labeling schemes
• Interval routing in some planar networks.

Cites work

• A linear time algorithm for finding tree-decompositions of small treewidth
• Designing networks with compact routing tables
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3906520 (Why is no real title available?)
• Labelling and Implicit Routing in Networks
• Nonconstructive tools for proving polynomial-time decidability
• ON DISJOINT CYCLES
• On Linear Time Minor Tests with Depth-First Search
• On search, decision, and the efficiency of polynomial-time algorithms
• Quickly excluding a forest
• The Pathwidth and Treewidth of Cographs
• Treewidth. Computations and approximations

This page was built for publication: On Interval Routing Schemes and treewidth

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