Hardness and approximation of minimum maximal matchings (Q2935383): Difference between revisions

@@ Property / cites work @@
+Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for NP-complete problems on planar graphs
+Normal rank
@@ Property / cites work @@
+Improved approximation bounds for edge dominating set in dense graphs
+Normal rank
@@ Property / cites work @@
+Approximation hardness of edge dominating set problems
+Normal rank
@@ Property / cites work @@
+A 2-approximation algorithm for the minimum weight edge dominating set problem
+Normal rank
@@ Property / cites work @@
+A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
+Normal rank
@@ Property / cites work @@
+An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
+Normal rank
@@ Property / cites work @@
+Minimum Edge Dominating Sets
@@ Property / cites work: Minimum Edge Dominating Sets / rank @@
+Normal rank
@@ Property / cites work @@
+The edge domination problem
@@ Property / cites work: The edge domination problem / rank @@
+Normal rank
@@ Property / cites work @@
+An Analysis of the Greedy Heuristic for Independence Systems
+Normal rank
@@ Property / cites work @@
+An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem
+Normal rank
@@ Property / cites work @@
+Minimum-maximal matching in series-parallel graphs
+Normal rank
@@ Property / cites work @@
+Approximating edge dominating set in dense graphs
@@ Property / cites work: Approximating edge dominating set in dense graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Edge domination on bipartite permutation graphs and cotriangulated graphs
+Normal rank
@@ Property / cites work @@
+Randomly matchable graphs
@@ Property / cites work: Randomly matchable graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Edge Dominating Sets in Graphs
@@ Property / cites work: Edge Dominating Sets in Graphs / rank @@
+Normal rank