Fixing improper colorings of graphs
From MaRDI portal
Publication:1698729
DOI10.1016/j.tcs.2017.11.013zbMath1386.68069arXiv1607.06911WikidataQ62595886 ScholiaQ62595886MaRDI QIDQ1698729
Konstanty Junosza-Szaniawski, Pedro Montealegre, Paweł Rzążewski, Valentin Garnero, Mathieu Liedloff
Publication date: 16 February 2018
Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1607.06911
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Fixing improper colorings of graphs, Introduction to reconfiguration, On the complexity of restoring corrupted colorings
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of reconfiguration problems
- Reoptimization of the shortest common superstring problem
- Reoptimization of minimum and maximum traveling salesman's tours
- Which problems have strongly exponential complexity?
- Fixing improper colorings of graphs
- Connectedness of the graph of vertex-colourings
- New Reoptimization Techniques applied to Steiner Tree Problem
- A Theory and Algorithms for Combinatorial Reoptimization
- Finding paths between 3-colorings
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- Mixing 3-Colourings in Bipartite Graphs
- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
- Set Partitioning via Inclusion-Exclusion
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- Parameterized Algorithms
- On the complexity of \(k\)-SAT
