Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs

DOI10.21494/iste.op.2023.0903zbMath1520.05056arXiv1610.00853MaRDI QIDQ6136471

Samiappan Dhanalakshmi, N. Sadagopan

Publication date: 31 August 2023

Published in: Advances in Pure and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1610.00853

zbMATH Keywords

Steiner treefeedback vertex set\(2K_2\)-free graphsodd (Even) cycle transversalstrictly chordality-\(k\) graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Distance in graphs (05C12) Transversal (matching) theory (05D15) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Dominating sets for split and bipartite graphs
• Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs
• The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
• Hamiltonian circuits in interval graph generalizations
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The complexity of generalized clique covering
• Graphs with no induced \(C_ 4\) and \(2K_ 2\)
• On strictly chordality-\(k\) graphs
• Steiner trees, connected domination and strongly chordal graphs
• Dominating Sets in Chordal Graphs
• Parameterized Algorithms for Even Cycle Transversal
• Node-and edge-deletion NP-complete problems
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs