%0 Journal Article %1 journals/ipl/ChaplickFMR18 %A Chaplick, Steven %A Fürst, Maximilian %A Maffray, Frédéric %A Rautenbach, Dieter %D 2018 %J Information Processing Letters %K journal myown publication %P 60--63 %R https://doi.org/10.1016/j.ipl.2018.07.008 %T On some graphs with a unique perfect matching %U http://www.sciencedirect.com/science/article/pii/S0020019018301558 %V 139 %X 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.

@article{journals/ipl/ChaplickFMR18, 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.}, added-at = {2018-07-25T14:41:18.000+0200}, author = {Chaplick, Steven and Fürst, Maximilian and Maffray, Frédéric and Rautenbach, Dieter}, biburl = {https://www.bibsonomy.org/bibtex/21746362b1f27e6c59085a757aecfcd30/chaplick}, doi = {https://doi.org/10.1016/j.ipl.2018.07.008}, interhash = {801fbd01f4b551eafcd8e66c2d8d8a3d}, intrahash = {1746362b1f27e6c59085a757aecfcd30}, issn = {0020-0190}, journal = {Information Processing Letters}, keywords = {journal myown publication}, pages = {60--63}, timestamp = {2019-01-18T09:40:46.000+0100}, title = {On some graphs with a unique perfect matching}, url = {http://www.sciencedirect.com/science/article/pii/S0020019018301558}, volume = 139, year = 2018 }