Paper Info
Title
O(n) Time Algorithms for Dominating Induced Matching Problems.
Abstract
We describe O(n) time algorithms for finding the minimum weighted dominating induced matching of chordal, dually chordal, biconvex, and claw-free graphs. For the first three classes, we prove tight O(n) bounds on the maximum number of edges that a graph having a dominating induced matching may contain. By applying these bounds, countings and employing existing O(n + m) time algorithms we show that they can be reduced to O(n) time. For claw-free graphs, we describe an algorithm based on that by Cardoso, Korpelainen and Lozin [4], for solving the unweighted version of the problem, which decreases its complexity from O(n(2)) to O(n), while additionally solving the weighted version.
Year
DOI
Venue
2014
10.1007/978-3-642-54423-1_35
Lecture Notes in Computer Science
Keywords
Field
DocType
algorithms,dominating induced matchings,graph theory
Graph theory,Graph,Discrete mathematics,Combinatorics,Computer science,Chordal graph,Algorithm
Conference
Volume
ISSN
Citations 
8392
0302-9743
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Min Chih Lin125921.22
Michel J. Mizrahi2222.98
Jayme Luiz Szwarcfiter361895.79