TY - GEN

T1 - Constructive linear time algorithms for small cutwidth and carving-width

AU - Thilikos, Dimitrios M.

AU - Serna, Maria J.

AU - Bodlaender, Hans L.

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.

PY - 2000

Y1 - 2000

N2 - 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 χ mapping the vertices of G to the leaves of T such that for any edge of T, the number of edges of G whose end-points have preimages in diffierent 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, χ) in case of an affirmative answer.

AB - 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 χ mapping the vertices of G to the leaves of T such that for any edge of T, the number of edges of G whose end-points have preimages in diffierent 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, χ) in case of an affirmative answer.

UR - http://www.scopus.com/inward/record.url?scp=84949808487&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84949808487&partnerID=8YFLogxK

U2 - 10.1007/3-540-40996-3_17

DO - 10.1007/3-540-40996-3_17

M3 - Conference contribution

AN - SCOPUS:84949808487

SN - 3540412557

SN - 9783540412557

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 192

EP - 203

BT - Algorithms and Computation - 11th International Conference, ISAAC 2000, Proceedings

A2 - Lee, D.T.

A2 - Teng, Shang-Hua

A2 - Teng, Shang-Hua

PB - Springer Verlag

T2 - 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000

Y2 - 18 December 2000 through 20 December 2000

ER -