Complexity of approximating the maximum and minimum maximal induced matchings

Valery Gordon, Y. Orlovich, Gerd Finke, I. Zverovich

Type: Preprint

Publication Date: 2007-01-01

Citations: 0

Locations

HAL (Le Centre pour la Communication Scientifique Directe) - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Bounding and approximating minimum maximal matchings in regular graphs	2020	Julien Baste Maximilian Fürst Michael A. Henning Elena Mohr Dieter Rautenbach
+ PDF Chat	Tight Approximation Ratio for Minimum Maximal Matching	2019	Szymon Dudycz Mateusz Lewandowski Jan Marcinkowski
+ PDF Chat	Maximum Induced Matching Algorithms via Vertex Ordering Characterizations	2019	Michel Habib Lalla Mouatadid
+	Number of Induced Matchings of Graphs	2021	Yan Chen Yan Liu
+	On complexity of special maximum matchings constructing	2007	Rafayel R. Kamalian Vahan Mkrtchyan
+ PDF Chat	Approximation by lexicographically maximal solutions in matching and matroid intersection problems	2022	Kristóf Bérczi Tamás Király Yutaro Yamaguchi Yu Yokoi
+	A Las Vegas O(n2.38 algorithm for the cardinality of a maximum matching	1994	Joseph Cheriyan
+	Exact Algorithms for Minimum Weighted Dominating Induced Matching	2015	Min Chih Lin Michel J. Mizrahi Jayme L. Szwarcfiter
+ PDF Chat	Rank-Maximal Matchings – Structure and Algorithms	2014	Pratik Ghosal Meghana Nasre Prajakta Nimbhorkar
+	Rank-maximal matchings – structure and algorithms	2018	Pratik Ghosal Meghana Nasre Prajakta Nimbhorkar
+	Maximum Induced Matchings for Chordal Graphs in Linear Time	2007	Andreas Brandstädt Chı́nh T. Hoàng
+	Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph	2007	Michael A. Henning Anders Yeo
+	The graphs with maximum induced matching and maximum matching the same size	2005	Kathie Cameron Tracy Walker
+	The average size of maximal matchings in graphs	2024	Alain Hertz Sébastien Bonte Gauvain Devillez Hadrien Mélot
+	A Linear Algorithm for Computing of a Minimum Weight Maximal Induced Matching in an Edge-Weighted Tree	2006	Victor Lepin
+	Maximum Matching	2015	Marcin Mucha
+	Maximum Matching	2016	Marcin Mucha
+	Extremal graphs for average sizes of maximal matchings	2023	John Engbers Aysel Erey
+ PDF Chat	Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs	2014	Danny Hermelin Matthias Mnich Erik Jan van Leeuwen
+ PDF Chat	Parameterized Complexity of Computing Maximum Minimal Blocking and Hitting Sets	2022	Júlio Araújo Marin Bougeret Víctor Campos Ignasi Sau

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors