| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6874118 | Information Processing Letters | 2018 | 12 Pages |
Abstract
Combining known results it follows that deciding whether a given graph G of size m has a unique perfect matching as well as finding that matching if it exists, can be done in time O(m) if G is either a cograph, or a split graph, or a claw-free graph. We provide structural insights concerning the graphs with a unique perfect matching that belong to these three graph classes, which lead to simple linear time algorithms for the unique perfect matching problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Steven Chaplick, Maximilian Fürst, Frédéric Maffray, Dieter Rautenbach,