Abstract
This paper addresses memory requirement issues arising in implementations of algorithms on graphs of bounded treewidth. Such dynamic programming algorithms require a large data table for each vertex of a tree-decomposition T of the input graph. We give a lineartime algorithm that finds the traversal order of T minimizing the number of tables stored simultaneously. We show that this minimum value is lower-bounded by the pathwidth of T plus one, and upper bounded by twice the pathwidth of T plus one. We also give a linear-time algorithm finding the depth-first traversal order minimizing the sum of the sizes of tables stored simultaneously.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
B.Aspvall, A.Proskurowski and J.A.Telle, Memory requirements for table computations in partial k-tree algorithms, submitted special issue of Algorithmica on Treewidth, Graph Minors and Algorithms.
T. Beyer, S.M. Hedetniemi, S.T. Hedetniemi and A. Proskurowski, Graph traversal with minimum stack depth, Congressus Numerantium, Vol. 32, 121–130, 1981.
H. Bodlaender, J. Gustedt and J.A. Telle, Linear-time register allocation for a fixed number of registers and no stack variables, Proceedings 9th ACM-SIAM Symposium on Discrete Algorithms (SODA'98), 574–583.
H. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth, in Proceedings 25th Symposium on the Theory of Computing (STOC'93), 226–234.
H. Bodlaender, A tourist guide through treewidth, Acta Cybernetica, 11:1–21, 1993.
Y.-J. Chiang, M.T. Goodrich, E.F. Grove, R. Tamassia, D.E. Vengroff and J.S.Vitter, External-Memory Graph Algorithms, Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA'95), pp. 139–149, 1995.
J.A. Ellis, I.H. Sudborough and J.S. Turner, The vertex separation number and search number of a graph, Information and Computation vol. 113, 50–79, 1994.
B. Hiim, Implementing and testing algorithms for tree-like graphs, Master's Thesis, November 1997, Dept. of Informatics, University of Bergen.
L. Kirousis and C. Papadimitriou, Searching and pebbling, Theoretical Computer Science 47, 205–218, 1986.
R. Möhring, Graph problems related to gate matrix layout and PLA folding, in Computational Graph Theory, Computing Suppl. 7, Springer-Verlag, 17–51, 1990.
A. Parra, Triangulating multitolerance graphs, Technical Report 392/1994, TU Berlin, Germany, 1994.
N. Robertson and P. Seymour, Graph Minors I. Excluding a forest, Journal of Combinatorial Theory Series B 35, 39–61, 1983.
P. Scheffler, A linear algorithm for the pathwidth of trees, Topics in Combinatorics and Graph Theory, Physica-Verlag Heidelberg, 613–620, 1990.
J.A. Telle and A. Proskurowski, Algorithms for vertex partitioning problems on partial k-trees, SIAM Journal on Discrete Mathematics, Vol. 10, No. 4, 529–550, November 1997.
M. Thorup, Structured Programs have Small Tree-Width and Good Register Allocation, Proceedings 23rd Workshop on Graph-Theoretical Concepts in Computer Science (WG'97), LNCS vol. 1335, 318–332.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aspvall, B., Proskurowski, A., Telle, J.A. (1998). Memory requirements for table computations in partial k-tree algorithms. In: Arnborg, S., Ivansson, L. (eds) Algorithm Theory — SWAT'98. SWAT 1998. Lecture Notes in Computer Science, vol 1432. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054370
Download citation
DOI: https://doi.org/10.1007/BFb0054370
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64682-2
Online ISBN: 978-3-540-69106-8
eBook Packages: Springer Book Archive