|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Complexity of Steiner Tree in Split Graphs - Dichotomy Results | | Madhu Illuri
; P. Renjith
; N. Sadagopan
; | | Date: |
5 Nov 2015 | | Abstract: | Given a connected graph $G$ and a terminal set $R subseteq V(G)$, {em
Steiner tree} asks for a tree that includes all of $R$ with at most $r$ edges
for some integer $r geq 0$. It is known from [ND12,Garey et. al] that Steiner
tree is NP-complete in general graphs. {em Split graph} is a graph which can
be partitioned into a clique and an independent set. K. White et. al has
established that Steiner tree in split graphs is NP-complete. In this paper, we
present an interesting dichotomy: we show that Steiner tree on $K_{1,4}$-free
split graphs is polynomial-time solvable, whereas, Steiner tree on
$K_{1,5}$-free split graphs is NP-complete. We investigate $K_{1,4}$-free and
$K_{1,3}$-free (also known as claw-free) split graphs from a structural
perspective. Further, using our structural study, we present polynomial-time
algorithms for Steiner tree in $K_{1,4}$-free and $K_{1,3}$-free split graphs.
Although, polynomial-time solvability of $K_{1,3}$-free split graphs is implied
from $K_{1,4}$-free split graphs, we wish to highlight our structural
observations on $K_{1,3}$-free split graphs which may be used in other
combinatorial problems. | | Source: | arXiv, 1511.1668 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER