Retracting Graphs to Cycles
From MaRDI portal
Publication:5091228
DOI10.4230/LIPIcs.ICALP.2019.70OpenAlexW2965843841MaRDI QIDQ5091228
Ravi Sundaram, Mehraneh Liaee, Rajmohan Rajaraman, Bruce M. Maggs, Debmalya Panigrahi, Samuel Haney
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1904.11946
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Hardness results for approximating the bandwidth
- Theory of semidefinite programming for sensor network localization
- A retraction problem in graph theory
- List homomorphisms to reflexive graphs
- Minimum 0-extensions of graph metrics
- Approximating the bandwidth via volume respecting embeddings
- Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
- \(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
- Retractions to Pseudoforests
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- Covering Problems with Hard Capacities
- Approximation algorithms for classification problems with pairwise relationships
- On Earthmover Distance, Metric Labeling, and 0-Extension
- Low Distortion Maps Between Point Sets
- Fixed-edge theorem for graphs with loops
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial Time
- Compaction, Retraction, and Constraint Satisfaction
- Approximation Algorithms for the 0-Extension Problem
- Distance-Preserving Graph Contractions
- A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
This page was built for publication: Retracting Graphs to Cycles
