Retracting Graphs to Cycles

DOI10.4230/LIPICS.ICALP.2019.70MaRDI QIDQ5091228zbMATH OpenOpenAlexFDO

Authors Samuel Haney, Mehraneh Liaee, Bruce M. Maggs, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1904.11946

zbMATH Keywords

approximation algorithmsgraph algorithmsgraph embeddingplanar graphs

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Recommendations

• A retraction problem in graph theory
• scientific article; zbMATH DE number 40997
• Algorithms for low-distortion embeddings into arbitrary 1-dimensional spaces
• Computing the stretch of an embedded graph
• Minimum Length Embedding of Planar Graphs at Fixed Vertex Locations

Cites work

• \(d\)-dimensional arrangement revisited
• A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
• A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
• A retraction problem in graph theory
• Approximating the bandwidth via volume respecting embeddings
• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Approximation Algorithms for the 0-Extension Problem
• Combinatorial optimization in VLSI design
• Compaction, Retraction, and Constraint Satisfaction
• Covering Problems with Hard Capacities
• Distance-Preserving Graph Contractions
• Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
• Fixed-edge theorem for graphs with loops
• Hardness results for approximating the bandwidth
• scientific article; zbMATH DE number 1054727 (Why is no real title available?)
• scientific article; zbMATH DE number 2079348 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 1833416 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 1445378 (Why is no real title available?)
• scientific article; zbMATH DE number 3219506 (Why is no real title available?)
• Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
• List homomorphisms to reflexive graphs
• Low Distortion Maps Between Point Sets
• Minimum 0-extensions of graph metrics
• On earthmover distance, metric labeling, and 0-extension
• Retractions to Pseudoforests
• Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
• Theory of semidefinite programming for sensor network localization

This page was built for publication: Retracting Graphs to Cycles

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