Cutwidth of Split Graphs and Threshold Graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Heggernes, P.
Lokshtanov, D.
Mihai, R.
Papadopoulos, C.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Society for Industrial and Applied Mathematics
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Siam Journal on Discrete Mathematics
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
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.
Περιγραφή
Λέξεις-κλειδιά
cutwidth, bisection width, threshold graphs, split graphs, min-cut, linear arrangement, interval-graphs, layout problems, trees, algorithm
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
<Go to ISI>://000295398200024
http://epubs.siam.org/sidma/resource/1/sjdmec/v25/i3/p1418_s1?isAuthorized=no
http://epubs.siam.org/sidma/resource/1/sjdmec/v25/i3/p1418_s1?isAuthorized=no
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών