Faster Exact Bandwidth
From MaRDI portal
Publication:5302047
DOI10.1007/978-3-540-92248-3_10zbMath1202.05135OpenAlexW2168800311MaRDI QIDQ5302047
Publication date: 20 January 2009
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_10
Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (6)
Bandwidth and distortion revisited ⋮ Capacitated domination faster than \(O(2^n)\) ⋮ A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs ⋮ An exact algorithm for minimum distortion embedding ⋮ Exact and approximate bandwidth ⋮ An Exponential Time 2-Approximation Algorithm for Bandwidth
Cites Work
- Unnamed Item
- Approximating the bandwidth via volume respecting embeddings
- Beyond NP-completeness for problems of bounded width (extended abstract)
- The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- Computing the Bandwidth of Interval Graphs
- The Bandwidth of Caterpillars with Hairs of Length 1 and 2
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- Complexity Results for Bandwidth Minimization
This page was built for publication: Faster Exact Bandwidth