Distortion is fixed parameter tractable

DOI10.1145/2489789MaRDI QIDQ2947587zbMATH OpenOpenAlexWikidataFDO

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

Publication date 24 September 2015

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2489789

zbMATH Keywords

treeembeddingdistortionparameterized algorithms

Mathematics Subject Classification ID

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

(11)

• Decomposing a graph into shortest paths with bounded eccentricity
• An exact algorithm for minimum distortion embedding
• Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
• An exact algorithm for minimum distortion embedding
• Slightly superexponential parameterized problems
• Decomposing a graph into shortest paths with bounded eccentricity
• Distortion Is Fixed Parameter Tractable
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• FPT algorithms for embedding into low complexity graphic metrics
• Line-distortion, bandwidth and path-length of a graph
• 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 Q2947587)