The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number (Q5387763): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1007/978-3-540-77120-3_25
+Normal rank
@@ Property / OpenAlex ID @@
+W1772739528
@@ Property / OpenAlex ID: W1772739528 / rank @@
+Normal rank
@@ Property / cites work @@
+O(√log n) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems
+Normal rank
@@ Property / cites work @@
+On approximating minimum vertex cover for graphs with perfect matching
+Normal rank
@@ Property / cites work @@
+Improved Parameterized Upper Bounds for Vertex Cover
+Normal rank
@@ Property / cites work @@
+Independence numbers of graphs - an extension of the Koenig-Egervary theorem
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating minimum vertex cover
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for Steiner and Directed Multicuts
+Normal rank
@@ Property / cites work @@
+Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
+Normal rank
@@ Property / cites work @@
+Clique is hard to approximate within \(n^{1-\epsilon}\)
+Normal rank
@@ Property / cites work @@
+Parameterizing MAX SNP Problems Above Guaranteed Values
+Normal rank
@@ Property / cites work @@
+Q5710169
@@ Property / cites work: Q5710169 / rank @@
+Normal rank
@@ Property / cites work @@
+Finding odd cycle transversals.
@@ Property / cites work: Finding odd cycle transversals. / rank @@
+Normal rank
@@ Property / cites work @@
+A characterization of the graphs in which the transversal number equals the matching number
+Normal rank
@@ Property / cites work @@
+A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
+Normal rank
@@ Property / cites work @@
+Linear degree extractors and the inapproximability of max clique and chromatic number
+Normal rank