Constructive linear time algorithms for small cutwidth and carving-width. (English) Zbl 1044.68709

Thilikos, Dimitrios M.; Serna, Maria J.; Bodlaender, Hans L.

Lee, D. T. (ed.) et al., Algorithms and computation. 11th international conference, ISAAC 2000, Taipei, Taiwan, December 18–20, 2000. Proceedings. Berlin: Springer (ISBN 3-540-41255-7). Lect. Notes Comput. Sci. 1969, 192-203 (2000).

Summary: Consider the following problem: For any constant \(k\) and any input graph \(G\), check whether there exists a tree \(T\) with internal vertices of degree 3 and a bijection \(\chi\) mapping the vertices of \(G\) to the leaves of \(T\) such that for any edge of \(T\), the number of edges of \(G\) whose endpoints have preimages in different components of \(T-e\), is bounded by \(k\). This problem is known as the MINIMUM ROUTING TREE CONGESTION problem and is relevant to the design of minimum congestion telephone networks. If, in the above definition, we consider lines instead of trees with internal vertices of degree 3 and bijections mapping the vertices of \(G\) to all the vertices of \(T\), we have the well known MINIMUM CUT LINEAR ARRANGEMENT problem. Recent results of the Graph Minor series of Robertson and Seymour imply (non-constructively) that both these problems are fixed parameter tractable. In this paper we give a constructive proof of this fact. Moreover, the algorithms of our proof are optimal and able to output the corresponding pair \((T,\chi)\) in case of an affirmative answer.
For the entire collection see [Zbl 0952.00049].

MSC:

68R10	Graph theory (including graph drawing) in computer science
68M10	Network design and communication in computer systems
05C85	Graph algorithms (graph-theoretic aspects)
68W40	Analysis of algorithms