Bandwidth and distortion revisited

DOI10.1016/J.DAM.2011.10.032zbMATH Open1236.05196OpenAlexW1682888911MaRDI QIDQ412348FDOQ412348

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

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

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)

Cites Work

• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• Exact and approximate bandwidth
• Title not available (Why is that?)
• Even Faster Exact Bandwidth
• Expected Computation Time for Hamiltonian Path problem
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Exact and Approximate Bandwidth
• Distortion Is Fixed Parameter Tractable
• Faster Exact Bandwidth
• An exact algorithm for minimum distortion embedding

Cited In (7)

• An exponential time 2-approximation algorithm for bandwidth
• Slightly Superexponential Parameterized Problems
• An exact algorithm for minimum distortion embedding
• On the minimum eccentricity shortest path problem
• Tractabilities and intractabilities on geometric intersection graphs
• Title not available (Why is that?)
• Title not available (Why is that?)

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)