On interval routing schemes and treewidth

DOI10.1006/inco.1997.2669zbMath0892.68069OpenAlexW2102159495MaRDI QIDQ1383155

Dimitrios M. Thilikos, Jan van Leeuwen, Hans L. Bodlaender, Richard B. Tan

Publication date: 15 June 1998

Published in: Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

interval routing schemes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (10)

Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Algorithms, Complexity, and Hans ⋮ Minors in graphs of large \(\theta_r\)-girth ⋮ Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ Computing the largest bond and the maximum connected cut of a graph ⋮ Low Polynomial Exclusion of Planar Graph Patterns ⋮ Characterization results of all shortest paths interval routing schemes ⋮ A survey on interval routing ⋮ Algorithms and obstructions for linear-width and related search parameters ⋮ The complexity of the characterization of networks supporting shortest-path interval routing.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. V. Excluding a planar graph
• Designing networks with compact routing tables
• Quickly excluding a forest
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Quickly excluding a planar graph
• Treewidth. Computations and approximations
• On search, decision, and the efficiency of polynomial-time algorithms
• Graph minors. XIII: The disjoint paths problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Labelling and Implicit Routing in Networks
• Easy problems for tree-decomposable graphs
• Nonconstructive tools for proving polynomial-time decidability
• On Linear Time Minor Tests with Depth-First Search
• ON DISJOINT CYCLES
• The Pathwidth and Treewidth of Cographs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: On interval routing schemes and treewidth