Distortion Is Fixed Parameter Tractable

DOI10.1007/978-3-642-02927-1_39zbMath1248.68244OpenAlexW1590194775WikidataQ57359785 ScholiaQ57359785MaRDI QIDQ3638056

Daniel Lokshtanov, Frances A. Rosamond, Michael R. Fellows, Elena Losievskaja, Fedor V. Fomin, Saket Saurabh

Publication date: 14 July 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02927-1_39

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Pattern matching in doubling spaces ⋮ On the Minimum Eccentricity Shortest Path Problem ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ On the minimum eccentricity shortest path problem ⋮ Bandwidth and distortion revisited ⋮ Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An exact algorithm for minimum distortion embedding ⋮ Unnamed Item