Bandwidth and distortion revisited

DOI10.1016/J.DAM.2011.10.032MaRDI QIDQ412348zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Marcin Pilipczuk

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

bandwidthexact algorithmsdistortionexponential algorithms

Mathematics Subject Classification ID

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

Recommendations

• Linear discrepancy and bandwidth
• Exact and approximate bandwidth
• Exact and Approximate Bandwidth
• scientific article; zbMATH DE number 932427
• The Effective Bandwidth Problem Revisited
• On the effective bandwidth of sampled signals
• Effective bandwidths for stationary sources

Cites work

• scientific article; zbMATH DE number 1617243 (Why is no real title available?)
• An exact algorithm for minimum distortion embedding
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• Distortion Is Fixed Parameter Tractable
• Even faster exact bandwidth
• Exact and Approximate Bandwidth
• Exact and approximate bandwidth
• Expected Computation Time for Hamiltonian Path problem
• Faster Exact Bandwidth

Cited in

(10)

• An exponential time 2-approximation algorithm for bandwidth
• scientific article; zbMATH DE number 4120213 (Why is no real title available?)
• An exact algorithm for minimum distortion embedding
• Slightly superexponential parameterized problems
• Even faster exact bandwidth
• On the minimum eccentricity shortest path problem
• Tractabilities and intractabilities on geometric intersection graphs
• Line-distortion, bandwidth and path-length of a graph
• scientific article; zbMATH DE number 1775392 (Why is no real title available?)
• Line-distortion, bandwidth and path-length of a graph

This page was built for publication: Bandwidth and distortion revisited

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