Fully decomposable split graphs
Broersma, Hajo and Kratsch, Dieter and Woeginger, Gerhard J. (2009) Fully decomposable split graphs. In: 20th International Workshop on Combinatorial Algorithms, IWOCA 2009, June 28 - July 2 2009, Hradec nad Moravicí, Czech Republic.
Restricted to UT campus only: Request a copy
|Abstract:||We discuss various questions around partitioning a split graph into connected parts. Our main result is a polynomial time algorithm that decides whether a given split graph is fully decomposable, i.e., whether it can be partitioned into connected parts of order for every summing up to the order of the graph. In contrast, we show that the decision problem whether a given split graph can be partitioned into connected parts of order for a given partition of the order of the graph, is NP-hard.
|Item Type:||Conference or Workshop Item|
|Copyright:||© 2009 Springer|
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/71247|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page
Metis ID: 266492