Cutwidth of Split Graphs and Threshold Graphs
| dc.contributor.author | Heggernes, P. | en |
| dc.contributor.author | Lokshtanov, D. | en |
| dc.contributor.author | Mihai, R. | en |
| dc.contributor.author | Papadopoulos, C. | en |
| dc.date.accessioned | 2015-11-24T17:22:51Z | |
| dc.date.available | 2015-11-24T17:22:51Z | |
| dc.identifier.issn | 0895-4801 | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/12674 | |
| dc.rights | Default Licence | - |
| dc.subject | cutwidth | en |
| dc.subject | bisection width | en |
| dc.subject | threshold graphs | en |
| dc.subject | split graphs | en |
| dc.subject | min-cut | en |
| dc.subject | linear arrangement | en |
| dc.subject | interval-graphs | en |
| dc.subject | layout problems | en |
| dc.subject | trees | en |
| dc.subject | algorithm | en |
| dc.title | Cutwidth of Split Graphs and Threshold Graphs | en |
| heal.abstract | 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 |
| heal.access | campus | - |
| heal.fullTextAvailability | TRUE | - |
| heal.identifier.primary | Doi 10.1137/080741197 | - |
| heal.identifier.secondary | <Go to ISI>://000295398200024 | - |
| heal.identifier.secondary | http://epubs.siam.org/sidma/resource/1/sjdmec/v25/i3/p1418_s1?isAuthorized=no | - |
| heal.journalName | Siam Journal on Discrete Mathematics | en |
| heal.journalType | peer reviewed | - |
| heal.language | en | - |
| heal.publicationDate | 2011 | - |
| heal.publisher | Society for Industrial and Applied Mathematics | en |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.type | journalArticle | - |
| heal.type.el | Άρθρο Περιοδικού | el |
| heal.type.en | Journal article | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Papadopoulos-2011-Cutwidth of split graphs .pdf
- Μέγεθος:
- 248.24 KB
- Μορφότυπο:
- Adobe Portable Document Format
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.74 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: