Constructive linear time algorithms for small carving-width
Dimitrios M. Thilikos, José Antonio de la O Serna, Hans L. Bodlaender · 2000
Consider the following problem: For any constant k and any input graph G ,c heck whether there exists tree Y with internal vertices of degree 3 and bijection ! mapping the vertices of G to the leaves of Y such that for any edge of Y ,t he number of edges ofG whose endpoints have preimages in di! erent components of Y ! e ,i s bounded byk .T his problem is known as theMinimum Routing Tree Congestion problem and is relevant to the design of minimum congestion telephone networks. Recent results of the Graph Minor series of Robertson and Seymour imply (non-constructively) that this problem is fixed parameter tractable. In this paper we give constructive proof of this fact. Moreover, the algorithms of our proof are optimal and able to output the corresponding pair (Y,! ) in case of an a rmative answer.