Complexity of Steiner Tree in Split Graphs - Dichotomy Results

DOI10.1007/978-3-319-29221-2_27zbMath1437.05045arXiv1511.01668OpenAlexW3102873859MaRDI QIDQ2795958

N. Sadagopan, P. Renjith, Madhu Illuri

Publication date: 23 March 2016

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Connectivity (05C40)

Related Items (3)

Hamiltonicity in Split Graphs - A Dichotomy ⋮ On the algorithmic aspects of strong subcoloring ⋮ Vertex deletion on split graphs: beyond 4-hitting set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs
• A simple algorithm to find Hamiltonian cycles in proper interval graphs
• A linear time recognition algorithm for proper interval graphs
• Finding Hamiltonian circuits in interval graphs
• Hamiltonian circuits in interval graph generalizations
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• On the history of the Euclidean Steiner tree problem
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• Saving an epsilon
• Incompressibility through Colors and IDs
• Steiner trees, connected domination and strongly chordal graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Computing Steiner Minimal Trees
• The steiner problem in graphs

This page was built for publication: Complexity of Steiner Tree in Split Graphs - Dichotomy Results