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 -