On interval routing schemes and treewidth
From MaRDI portal
Publication:1383155
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
Related Items
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
