Decycling with a matching

Citation data:

Information Processing Letters, ISSN: 0020-0190, Vol: 124, Page: 26-29

Publication Year:
2017
Usage 133
Abstract Views 133
Social Media 8
Shares, Likes & Comments 8
DOI:
10.1016/j.ipl.2017.04.003
Author(s):
Carlos V.G.C. Lima, Dieter Rautenbach, Uéverton S. Souza, Jayme L. Szwarcfiter
Publisher(s):
Elsevier BV
Tags:
Mathematics, Computer Science
article description
As a natural variant of the many decycling notions studied in graphs, we consider the problem to decide whether a given graph G has a matching M such that G−M is a forest. We establish NP-completeness of this problem for 2-connected planar subcubic graphs, and describe polynomial time algorithms that also determine such a matching if it exists for graphs that are claw- and paw-free, P5 -free, chordal, and C4 -free distance hereditary.

This article has 0 Wikipedia mention.