Treewidth of Graphs
- PDF / 186,908 Bytes
- 3 Pages / 547.087 x 737.008 pts Page_size
- 33 Downloads / 184 Views
T
Treewidth of Graphs
7. Ferragina, P., Venturini, R.: A simple storage scheme for strings achieving entropy bounds. Theor. Comput. Sci. 372, (1):115– 121 (2007) 8. Geary, R., Raman, R., Raman, V.: Succinct ordinal trees with level-ancestor queries. In: Proc. 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1–10. New Orleans, USA (2004) 9. He, M., Munro, J.I., Rao, S.S.: Succinct ordinal trees based on tree covering. In: Proc. 34th International Colloquium on Algorithms, Language and Programming (ICALP). LNCS n. 4596, pp. 509–520. Springer, Wroclaw, Poland (2007) 10. Jacobson, G.: Space-efficient static trees and graphs. In: Proc. 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 549–554. Triangle Park, USA (1989) 11. Jansson, J., Sadakane, K., Sung, W.: Ultra-succinct representation of ordered trees. In: Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 575–584. New Orleans, USA(2007) 12. Kosaraju, S.R.: Efficient tree pattern matching. In: Proc. 20th IEEE Foundations of Computer Science (FOCS), pp. 178–183. Triangle Park, USA (1989) 13. Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762–776 (2001) 14. Navarro, G., Mäkinen, V.: Compressed full text indexes. ACM Comput. Surv. 39(1) (2007) 15. Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applications to encoding k-ary trees and multisets. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 233–242. San Francisco, USA (2002)
Treewidth of Graphs 1987; Arnborg, Corneil, Proskurowski HANS L. BODLAENDER Institute of Information and Computing Sciences Algorithms and Complexity Group, Center for Algorithmic Systems, University of Utrecht, Utrecht, The Netherlands Keywords and Synonyms Partial k-tree; Dimension; k-decomposable graphs Problem Definition The treewidth of graphs is defined in terms of tree decompositions. A tree decomposition of a graph G = (V ; E) is a pair (fX i ji 2 Ig; T = (I; F)) with fX i ji 2 Ig a collection of subsets of V, called bags, and T a tree, such that S i2I X i = V. For all fv; wg 2 E, there is an i 2 I with v; w 2 X i . For all v 2 V, the set fi 2 Ijv 2 X i g induces a connected subtree of T.
Treewidth of Graphs, Figure 1 A graph and a tree decomposition of width 2
The width of a tree decomposition is max i2I jX i j 1, and the treewidth of a graph G is the minimum width of a tree decomposition of G. An alternative definition is in terms of chordal graphs. A graph G = (V; E) is chordal, if and only if each cycle of length at least 4 has a chord, i. e., an edge between two vertices that are not successive on the cycle. A graph G has treewidth at most k, if and only if G is a subgraph of a chordal graph H that has maximum clique size at most k. A third alternative definition is in terms of orderings of the vertices. Let be a permutation (called elimination scheme in this context) of the vertices of G = (V ; E). Repeat the following step for i = 1; : : : ; jVj: take vertex (i), turn the se
Data Loading...
