Cutwidth of Split Graphs and Threshold Graphs (Journal article)

Heggernes, P./ Lokshtanov, D./ Mihai, R./ Papadopoulos, C.

We give a linear-time algorithm to compute the cutwidth of threshold graphs, thereby resolving the computational complexity of cutwidth on this graph class. Threshold graphs are a well-studied subclass of interval graphs and of split graphs, both of which are unrelated subclasses of chordal graphs. To complement our result, we show that cutwidth is NP-complete on split graphs, and consequently also on chordal graphs. The cutwidth of interval graphs is still open, and only very few graph classes are known so far on which polynomial-time cutwidth algorithms exist. Thus we contribute to define the border between graph classes on which cutwidth is polynomially solvable and on which it remains NP-complete.
Institution and School/Department of submitter: Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Keywords: cutwidth,bisection width,threshold graphs,split graphs,min-cut,linear arrangement,interval-graphs,layout problems,trees,algorithm
ISSN: 0895-4801
Link: <Go to ISI>://000295398200024
Publisher: Society for Industrial and Applied Mathematics
Appears in Collections:Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)

Files in This Item:
File Description SizeFormat 
Papadopoulos-2011-Cutwidth of split graphs .pdf248.24 kBAdobe PDFView/Open

 Please use this identifier to cite or link to this item:
  This item is a favorite for 0 people.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.