Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/12674Full metadata record
| DC Field | Value | Language |
|---|---|---|
| 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.type | journalArticle | - |
| heal.type.en | Journal article | en |
| heal.type.el | Άρθρο Περιοδικού | el |
| 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.language | en | - |
| heal.access | campus | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών | el |
| heal.publicationDate | 2011 | - |
| 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.publisher | Society for Industrial and Applied Mathematics | en |
| heal.journalName | Siam Journal on Discrete Mathematics | en |
| heal.journalType | peer reviewed | - |
| heal.fullTextAvailability | TRUE | - |
| Appears in Collections: | Άρθρα σε επιστημονικά περιοδικά ( Ανοικτά). ΜΑΘ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Papadopoulos-2011-Cutwidth of split graphs .pdf | 248.24 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
