On the complexity of restoring corrupted colorings
From MaRDI portal
Publication:2424718
DOI10.1007/s10878-018-0342-2zbMath1420.05056arXiv1701.01939OpenAlexW2963087661WikidataQ129269767 ScholiaQ129269767MaRDI QIDQ2424718
Publication date: 25 June 2019
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1701.01939
computational complexitylocal searchgraph coloringparameterized complexitycombinatorial reconfiguration
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Local search: is brute-force avoidable?
- The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
- On the complexity of some colorful problems parameterized by treewidth
- On a hypercube coloring problem
- NP is as easy as detecting unique solutions
- Some simplified NP-complete graph problems
- Reconfiguration in bounded bandwidth and tree-depth
- Fixing improper colorings of graphs
- The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
- Finding Shortest Paths Between Graph Colourings
- On the hardness of losing weight
- Set Partitioning via Inclusion-Exclusion
- The complexity of promise problems with applications to public-key cryptography
- The NP-completeness column: an ongoing guide
- Planar Formulae and Their Uses
- Determining the thickness of graphs is NP-hard
- Fine-grained complexity analysis of two classic TSP variants
- On Local Search and Placement of Meters in Networks
- Kernelization Lower Bounds by Cross-Composition
- Parameterized Algorithms
- Exploring the complexity boundary between coloring and list-coloring
- Computational Complexity
- On the complexity of \(k\)-SAT
This page was built for publication: On the complexity of restoring corrupted colorings
