Cutwidth of Split Graphs and Threshold Graphs

Το τεκμήριο παρέχεται από τον φορέα :

Αποθετήριο :
Ιδρυματικό Αποθετήριο Ολυμπιάς

δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου^*

κοινοποιήστε το τεκμήριο

Σημασιολογικός εμπλουτισμός από το EKT

ΕΚΤ τύπος τεκμηρίου

ΕΚΤ xρονολογία

2011 (EL)

EKT Ιστορική περίοδος

Τίτλος

Cutwidth of Split Graphs and Threshold Graphs (EN)

Δημιουργός

Heggernes, P. (EN)

Συντελεστής

Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών (EL)

Heggernes, P. (EN)

Περιγραφή

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. (EN)

Θέμα

cutwidth (EN)

Πάροχος

Πανεπιστήμιο Ιωαννίνων

Αποθετήριο / συλλογή

Ιδρυματικό Αποθετήριο Ολυμπιάς

Επιμέρους συλλογή

Σχολή Θετικών Επιστημών

Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά)

ΑΠΟΘΕΤΗΡΙΟ "ΟΛΥΜΠΙΑΣ"

Τμήμα Μαθηματικών

Περιοδικό