Bandwidth and distortion revisited

DOI10.1016/j.dam.2011.10.032zbMath1236.05196OpenAlexW1682888911MaRDI QIDQ412348

Marcin Pilipczuk, Marek Cygan

Publication date: 4 May 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2011.10.032

zbMATH Keywords

bandwidthdistortionexact algorithmsexponential algorithms

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the minimum eccentricity shortest path problem, An exponential time 2-approximation algorithm for bandwidth, Tractabilities and intractabilities on geometric intersection graphs, An exact algorithm for minimum distortion embedding, Slightly Superexponential Parameterized Problems

Cites Work

• Unnamed Item
• Unnamed Item
• An exact algorithm for minimum distortion embedding
• Exact and approximate bandwidth
• Beyond NP-completeness for problems of bounded width (extended abstract)
• Even Faster Exact Bandwidth
• Exact and Approximate Bandwidth
• Distortion Is Fixed Parameter Tractable
• Expected Computation Time for Hamiltonian Path problem
• Faster Exact Bandwidth