FPT Algorithms for Embedding into Low-Complexity Graphic Metrics

DOI10.1145/3369933MaRDI QIDQ5053040zbMATH OpenOpenAlexWikidataFDO

Authors Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra

Publication date 5 December 2022

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

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

zbMATH Keywords

dynamic programmingFPTlow-distortion embeddingsmetric embeddingmetric spaces

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Metric embeddings as related to computational problems and algorithms (68R12) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• FPT algorithms for embedding into low complexity graphic metrics
• scientific article; zbMATH DE number 7740887
• Embedding planar graphs into low-treewidth graphs with applications to efficient approximation schemes for metric problems
• On optimal embeddings of metrics in graphs
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Tight lower bounds on graph embedding problems
• The complexity of low-distortion embeddings between point sets
• scientific article; zbMATH DE number 3914341
• scientific article; zbMATH DE number 3995712

Cited in

(3)

• Distortion is fixed parameter tractable
• Distortion Is Fixed Parameter Tractable
• FPT algorithms for embedding into low complexity graphic metrics

This page was built for publication: FPT Algorithms for Embedding into Low-Complexity Graphic Metrics

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