Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms (Q411835): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2012700732
@@ Property / OpenAlex ID: W2012700732 / rank @@
+Normal rank
@@ Property / cites work @@
+Proof verification and the hardness of approximation problems
+Normal rank
@@ Property / cites work @@
+Q4258216
@@ Property / cites work: Q4258216 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4252376
@@ Property / cites work: Q4252376 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3941433
@@ Property / cites work: Q3941433 / rank @@
+Normal rank
@@ Property / cites work @@
+On approximation properties of the Independent set problem for degree 3 graphs
+Normal rank
@@ Property / cites work @@
+An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
+Normal rank
@@ Property / cites work @@
+Efficient approximation of Min Set Cover by moderately exponential algorithms
+Normal rank
@@ Property / cites work @@
+A Bottom-Up Method and Fast Algorithms for max independent set
+Normal rank
@@ Property / cites work @@
+Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
+Normal rank
@@ Property / cites work @@
+On Parameterized Approximability
@@ Property / cites work: On Parameterized Approximability / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex Cover: Further Observations and Further Improvements
+Normal rank
@@ Property / cites work @@
+Exponential-time approximation of weighted set cover
+Normal rank
@@ Property / cites work @@
+Parameterized Approximation Problems
@@ Property / cites work: Parameterized Approximation Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Q2768314
@@ Property / cites work: Q2768314 / rank @@
+Normal rank
@@ Property / cites work @@
+Automata, Languages and Programming
@@ Property / cites work: Automata, Languages and Programming / rank @@
+Normal rank
@@ Property / cites work @@
+Q3396567
@@ Property / cites work: Q3396567 / rank @@
+Normal rank
@@ Property / cites work @@
+Exact exponential algorithms.
@@ Property / cites work: Exact exponential algorithms. / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002852
@@ Property / cites work: Q3002852 / rank @@
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
+Normal rank
@@ Property / cites work @@
+Vertex packings: Structural properties and algorithms
+Normal rank
@@ Property / cites work @@
+STACS 2005
@@ Property / cites work: STACS 2005 / rank @@
+Normal rank
@@ Property / cites work @@
+On Approximate Solutions for Combinatorial Optimization Problems
+Normal rank
@@ Property / cites work @@
+Confronting hardness using a hybrid approach
@@ Property / cites work: Confronting hardness using a hybrid approach / rank @@
+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
@@ Property / cites work @@
+Q4414647
@@ Property / cites work: Q4414647 / rank @@
+Normal rank
@@ Property / cites work @@
+Linear degree extractors and the inapproximability of max clique and chromatic number
+Normal rank