Distortion Is Fixed Parameter Tractable

DOI10.1007/978-3-642-02927-1_39MaRDI QIDQ3638056zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances Rosamond, 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

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

Recommendations

• Distortion is fixed parameter tractable
• Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
• FPT algorithms for embedding into low complexity graphic metrics
• FPT Algorithms for Embedding into Low-Complexity Graphic Metrics
• Low-distortion embeddings of general metrics into the line

Cited in

(15)

• Bandwidth and distortion revisited
• Pattern matching in doubling spaces
• On the minimum eccentricity shortest path problem
• Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs
• An exact algorithm for minimum distortion embedding
• What's next? Future directions in parameterized complexity
• Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
• Distortion is fixed parameter tractable
• An exact algorithm for minimum distortion embedding
• scientific article; zbMATH DE number 7758338 (Why is no real title available?)
• A treehouse with custom windows: minimum distortion embeddings into bounded treewidth graphs
• On the minimum eccentricity shortest path problem
• scientific article; zbMATH DE number 7758347 (Why is no real title available?)
• FPT algorithms for embedding into low complexity graphic metrics
• Distortion in several variables

This page was built for publication: Distortion Is Fixed Parameter Tractable

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