- Title
- Derivation of algorithms for cutwidth and related graph layout parameters
- Creator
- Bodlaender, Hans L.; Fellows, Michael R.; Thilikos, Dimitrios M.
- Relation
- Journal of Computer and System Sciences Vol. 75, Issue 4, p. 231-244
- Publisher Link
- http://dx.doi.org/10.1016/j.jcss.2008.10.003
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2009
- Description
- In this paper, we investigate algorithms for some related graph parameters. Each of these asks for a linear ordering of the vertices of the graph (or can be formulated as such), and constructive linear time algorithms for the fixed parameter versions of the problems have been published for several of these. Examples are cutwidth, pathwidth, and directed or weighted variants of these. However, these algorithms have complicated technical details. This paper attempts to present ideas in these algorithms in a different more easily accessible manner, by showing that the algorithms can be obtained by a stepwise modification of a trivial hypothetical non-deterministic algorithm. The methodology is applied to rederive known results for the cutwidth and the pathwidth problem, and obtain new results for several variants of these problems, like directed and weighted variants of cutwidth and modified cutwidth.
- Subject
- parameterized algorithms; layout parameters; cutwidth; pathwidth; modified cutwidth; finite state automata
- Identifier
- uon:7231
- Identifier
- http://hdl.handle.net/1959.13/806838
- Identifier
- ISSN:0022-0000
- Reviewed
- Hits: 2000
- Visitors: 1943
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|