Fully decomposable split graphs

H.J. Broersma, D. Kratsch, G.J. Woeginger

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)

Samenvatting

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 a 1,a 2,...,a k for every a 1,a 2,...,a k 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 a 1,a 2,...,a k for a given partition a 1,a 2,...,a k of the order of the graph, is NP-hard.
Originele taal-2Engels
TitelCombinatorial Algorithms (20th International Workshop, IWOCA 2009, Hradec nad Moravici, Czech Republic, June 28-July 2, 2009, Revised Selected Papers)
RedacteurenJ. Fiala, J. Kratochvil, M. Miller
Plaats van productieBerlin
UitgeverijSpringer
Pagina's105-112
ISBN van geprinte versie978-3-642-10216-5
DOI's
StatusGepubliceerd - 2009

Publicatie series

NaamLecture Notes in Computer Science
Volume5874
ISSN van geprinte versie0302-9743

Vingerafdruk

Duik in de onderzoeksthema's van 'Fully decomposable split graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit