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

decyclingfeedback vertex setgraph algorithmsmatching

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 1744105 (Why is no real title available?)
• Maximum induced trees in graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(10)

• Perfect matching cuts partitioning a graph into complementary subgraphs
• Feedback arc number and feedback vertex number of Cartesian product of directed cycles
• Bipartizing with a matching
• On the computational complexity of the bipartizing matching problem
• Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs
• Near-bipartiteness, connected near-bipartiteness, independent feedback vertex set and acyclic vertex cover on graphs having small dominating sets
• Near-bipartiteness on graphs having small dominating sets
• Perfect matching cuts partitioning a graph into complementary subgraphs
• The complexity of (P₃,H)-Arrowing and beyond
• Graph modification of bounded size to minor-closed classes as fast as vertex deletion

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)