Decycling with a matching

DOI10.1016/J.IPL.2017.04.003MaRDI QIDQ2628271zbMATH OpenOpenAlexFDO

Authors Dieter Rautenbach, Uéverton S. Souza, Carlos Vinícius G. C. Lima, Jayme L. Szwarcfiter

Publication date 13 June 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2017.04.003

zbMATH Keywords

matchinggraph algorithmsfeedback vertex setdecycling

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract)
• The complexity of the matching-cut problem for planar graphs and other graph classes
• Bipartizing with a matching
• Matching cutsets in graphs

Cites work

• scientific article; zbMATH DE number 1744105 (Why is no real title available?)
• Decycling graphs
• Distance-hereditary graphs
• Dominating and large induced trees in regular graphs
• Dominating subgraphs in graphs with some forbidden structures
• Feedback vertex sets in cubic multigraphs
• Maximum induced trees in graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(6)

• On the computational complexity of the bipartizing matching problem
• Bipartizing with a matching
• Near-bipartiteness, connected near-bipartiteness, independent feedback vertex set and acyclic vertex cover on graphs having small dominating sets
• Feedback arc number and feedback vertex number of Cartesian product of directed cycles
• Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs
• Perfect matching cuts partitioning a graph into complementary subgraphs

This page was built for publication: Decycling with a matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2628271)