Hardness and inapproximability of convex recoloring problems (Q2446103): Difference between revisions

@@ Property / author @@
-Manoel B. Campêlo
@@ Property / author: Manoel B. Campêlo / rank @@
-Normal rank
@@ Property / author @@
+Manoel B. Campêlo
@@ Property / author: Manoel B. Campêlo / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.tcs.2014.03.017
+Normal rank
@@ Property / OpenAlex ID @@
+W1971028618
@@ Property / OpenAlex ID: W1971028618 / rank @@
+Normal rank
@@ Property / cites work @@
+Algorithmic construction of sets for             <i>k</i>             -restrictions
+Normal rank
@@ Property / cites work @@
+On the structure of graphs with few \(P_4\)s
@@ Property / cites work: On the structure of graphs with few \(P_4\)s / rank @@
+Normal rank
@@ Property / cites work @@
+Improved approximation algorithm for convex recoloring of trees
+Normal rank
@@ Property / cites work @@
+Quadratic kernelization for convex recoloring of trees
+Normal rank
@@ Property / cites work @@
+Q5422499
@@ Property / cites work: Q5422499 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Complexity of Solving or Approximating Convex Recoloring Problems
+Normal rank
@@ Property / cites work @@
+Connected Coloring Completion for General Graphs: Algorithms and Complexity
+Normal rank
@@ Property / cites work @@
+Q4393480
@@ Property / cites work: Q4393480 / rank @@
+Normal rank
@@ Property / cites work @@
+The Rectilinear Steiner Tree Problem is $NP$-Complete
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of minimum convex coloring
@@ Property / cites work: The complexity of minimum convex coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Convex Recoloring Revisited: Complexity and Exact Algorithms
+Normal rank
@@ Property / cites work @@
+A tree representation for \(P_ 4\)-sparse graphs
@@ Property / cites work: A tree representation for \(P_ 4\)-sparse graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Convex recoloring of paths
@@ Property / cites work: Convex recoloring of paths / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient approximation of convex recolorings
@@ Property / cites work: Efficient approximation of convex recolorings / rank @@
+Normal rank
@@ Property / cites work @@
+Convex recolorings of strings and trees: Definitions, hardness results and algorithms
+Normal rank
@@ Property / cites work @@
+Partial convex recolorings of trees and galled networks
+Normal rank
@@ Property / cites work @@
+Non deterministic polynomial optimization problems and their approximations
+Normal rank
@@ Property / cites work @@
+Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems
+Normal rank
@@ Property / cites work @@
+Q4527015
@@ Property / cites work: Q4527015 / rank @@
+Normal rank
@@ Property / cites work @@
+A \(2^{O(k)}\)poly\((n)\) algorithm for the parameterized convex recoloring problem
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for metric facility location and             <i>k</i>             -Median problems using the primal-dual schema and Lagrangian relaxation
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:2446103