An O *(1.1939 n ) Time Algorithm for Minimum Weighted Dominating Induced Matching

Min Chih Lin, Michel J. Mizrahi, Jayme L. Szwarcfiter

Type: Book-Chapter

Publication Date: 2013-01-01

Citations: 8

DOI: https://doi.org/10.1007/978-3-642-45030-3_52

View Publication

Download PDF

Locations

Lecture notes in computer science - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Exact Algorithms for Minimum Weighted Dominating Induced Matching	2015	Min Chih Lin Michel J. Mizrahi Jayme L. Szwarcfiter
+	An $O^*(1.1939^n)$ time algorithm for minimum weighted dominating induced matching	2013	Min Chih Lin Michel J. Mizrahi Jayme L. Szwarcfiter
+	An $O^*(1.1939^n)$ time algorithm for minimum weighted dominating induced matching	2013	Min Chih Lin Michel J. Mizrahi Jayme L. Szwarcfiter
+	A Linear Algorithm for Computing of a Minimum Weight Maximal Induced Matching in an Edge-Weighted Tree	2006	Victor Lepin
+	Exact Algorithms for Dominating Induced Matching Based on Graph Partition	2014	Mingyu Xiao Hiroshi Nagamochi
+	Exact algorithms for dominating induced matchings	2013	Min Chih Lin Michel J. Mizrahi Jayme L. Szwarcfiter
+	Exact algorithms for dominating induced matching based on graph partition	2015	Mingyu Xiao Hiroshi Nagamochi
+	Complexity of approximating the maximum and minimum maximal induced matchings	2007	Valery Gordon Y. Orlovich Gerd Finke I. Zverovich
+ PDF Chat	An efficient matheuristic for the minimum-weight dominating set problem	2018	Mayra Carvalho Albuquerque Thibaut Vidal
+	A Las Vegas O(n2.38 algorithm for the cardinality of a maximum matching	1994	Joseph Cheriyan
+	Efficiency in exponential time for domination-type problems	2008	Ingo Schiermeyer
+ PDF Chat	An order-based algorithm for minimum dominating set with application in graph mining	2017	David Chalupa
+ PDF Chat	Weighted Triangle-free 2-matching Problem with Edge-disjoint Forbidden Triangles	2021	Yusuke Kobayashi
+ PDF Chat	Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles	2020	Yusuke Kobayashi
+	Dominating Induced Matchings for P7-Free Graphs in Linear Time	2011	Andreas Brandstädt Raffaele Mosca
+	Dominating Induced Matchings for P7-Free Graphs in Linear Time	2011	Andreas Brandstädt Raffaele Mosca
+	The Weighted Matching Approach to Maximum Cardinality Matching	2017	Harold N. Gabow
+	The Weighted Matching Approach to Maximum Cardinality Matching	2017	Harold N. Gabow
+	Algorithms with improved delay for enumerating connected induced subgraphs of a large cardinality	2023	Shanshan Wang Chenglong Xiao Emmanuel Casseau
+	Minimum weight perfect matching in O(1) parallel time	2013	Austin G. Fowler

Works That Cite This (6)

Action	Title	Year	Authors
+ PDF Chat	Perfect edge domination: hard and solvable cases	2017	Min Chih Lin Vadim Lozin Verónica Moyano Jayme L. Szwarcfiter
+ PDF Chat	Dominating induced matchings in graphs containing no long claw	2017	Alain Hertz Vadim Lozin Bernard Ries Viktor Zamaraev D. de Werra
+	Exact algorithms for dominating induced matching based on graph partition	2015	Mingyu Xiao Hiroshi Nagamochi
+ PDF Chat	The Maximum Number of Dominating Induced Matchings	2014	Min Chih Lin Veronica A. Moyano Dieter Rautenbach Jayme L. Szwarcfiter
+	Exact Algorithms for Minimum Weighted Dominating Induced Matching	2015	Min Chih Lin Michel J. Mizrahi Jayme L. Szwarcfiter
+	Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs	2014	Mingyu Xiao Hiroshi Nagamochi

Works Cited by This (8)

Action	Title	Year	Authors
+ PDF Chat	Hereditary Efficiently Dominatable Graphs	2012	Martin Milanič
+ PDF Chat	Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs	2012	Andreas Brandstädt Arne Leitert Dieter Rautenbach
+ PDF Chat	Dominating Induced Matchings for P 7-free Graphs in Linear Time	2011	Andreas Brandstädt Raffaele Mosca
+ PDF Chat	Fourier meets möbius: fast subset convolution	2007	Andreas Björklund Thore Husfeldt Petteri Kaski Mikko Koivisto
+	Efficient edge domination in regular graphs	2008	Domingos M. Cardoso Jorge Orestes Cerdeira Charles Delorme Pedro C. Silva
+	Exact algorithms for dominating induced matchings	2013	Min Chih Lin Michel J. Mizrahi Jayme L. Szwarcfiter
+ PDF Chat	Determinant Sums for Undirected Hamiltonicity	2010	Andreas Björklund
+	Dominating Induced Matchings for P7-Free Graphs in Linear Time	2011	Andreas Brandstädt Raffaele Mosca