TY - CHAP
T1 - Starting with nondeterminism
T2 - The systematic derivation of linear-time graph layout algorithms
AU - Bodlaender, Hans L.
AU - Fellows, Michael R.
AU - Thilikos, Dimitrios M.
PY - 2003
Y1 - 2003
N2 - This paper investigates algorithms for some related graph parameters. Each asks for a linear ordering of the vertices of the graph (or can be formulated as such), and there are constructive linear time algorithms for the fixed parameter versions of the problems. Examples are cutwidth, pathwidth, and directed or weighted variants of these. However, these algorithms have complicated technical details. This paper attempts to present 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 for a generalisation of the cutwidth problem to weighted mixed graphs. As a consequence, we obtain new algorithmic results for various problems like modified cutwidth, and rederive known results for other related problems with simpler proofs.
AB - This paper investigates algorithms for some related graph parameters. Each asks for a linear ordering of the vertices of the graph (or can be formulated as such), and there are constructive linear time algorithms for the fixed parameter versions of the problems. Examples are cutwidth, pathwidth, and directed or weighted variants of these. However, these algorithms have complicated technical details. This paper attempts to present 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 for a generalisation of the cutwidth problem to weighted mixed graphs. As a consequence, we obtain new algorithmic results for various problems like modified cutwidth, and rederive known results for other related problems with simpler proofs.
KW - Algorithm design methodology
KW - Algorithms and data structures
KW - Finite state automata
KW - Graph algorithms
KW - Graph layout problems
UR - http://www.scopus.com/inward/record.url?scp=21144433317&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=21144433317&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-45138-9_18
DO - 10.1007/978-3-540-45138-9_18
M3 - Chapter
AN - SCOPUS:21144433317
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 239
EP - 248
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Rovan, Branislav
A2 - Vojtas, Peter
PB - Springer Verlag
ER -