Abstract
Inspired by the heuristic algorithm for boolean-width by Telle et. al. [1], we develop a heuristic algorithm for rank-width. We compare results on graphs of practical relevance to the established bounds of boolean-width. While the width of most graphs is lower than the known values for tree-width, it turns out that the boolean-width heuristic is able to find decompositions of significantly lower width. In a second step we therefore present a further algorithm that can decide if for a graph G and a value k exists a rank-decomposition of width lower than k. This enables to show that boolean-width is in fact lower than or equal to rank-width on many of the investigated graphs.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Hvidevold, E.M., Sharmin, S., Telle, J.A., Vatshelle, M.: Finding Good Decompositions for Dynamic Programming on Dense Graphs. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 219–231. Springer, Heidelberg (2012)
Courcelle, B.: The monadic second-order logic of graphs i. recognizable sets of finite graphs. Information and Computation, 12–75 (1990)
Courcelle, B., Makowsky, J., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique width. Theory of Computing Systems 33, 125–150 (1999)
Langer, A., Reidl, F., Rossmanith, P., Sikdar, S.: Recent progress in practical aspects of mso model-checking (in preparation, 2012)
Bodlaender, H.L., Koster, A.M.: Treewidth computations i. upper bounds. Information and Computation 208(3), 259–275 (2010)
Hliněny, P., Oum, S.I., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Computer Journal, 10–1093 (2007)
Oum, S.I.: Approximating rank-width and clique-width quickly. ACM Trans. Algorithms 5(1), 10:1–10:20 (2008)
Bodlaender, H., van den Broek, J.W.: Treewidthlib: A benchmark for algorithms for treewidth and related graph problems (2004), http://www.cs.uu.nl/research/projects/treewidthlib/
Robertson, N., Seymour, P.: Graph minors. iii. planar tree-width. Journal of Combinatorial Theory, Series B 36(1), 49–64 (1984)
Robertson, N., Seymour, P.: Graph minors. x. obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B 52(2), 153–190 (1991)
Oum, S.I., Seymour, P.: Approximating clique-width and branch-width. J. Comb. Theory Ser. B 96, 514–528 (2006)
Bui-Xuan, B.M., Telle, J.A., Vatshelle, M.: Boolean-width of graphs. Theoretical Computer Science 412(39), 5187–5204 (2011)
Oum, S.I.: Rank-width is less than or equal to branch-width. Journal of Graph Theory 57(3), 239–244 (2008)
Knuth, D.E.: The Stanford GraphBase: a platform for combinatorial computing. ACM, New York (1993)
Johnson, D.J., Trick, M.A. (eds.): Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993. American Mathematical Society, Boston (1996)
Bell, J., Stevens, B.: A survey of known results and research areas for n-queens. Discrete Mathematics 309(1), 1–31 (2009)
Rlfap, E., Eindhoven, T.U., Group, R.: Euclid calma radio link frequency assignment project technical annex t-2.3.3: Local search (1995)
Bilmes, J.: Uai 2006 inference evaluation results. Technical report, University of Washington, Seattle (2006)
Oum, S.I.: Rank-width and vertex-minors. J. Comb. Theory Ser. B 95(1), 79–100 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Beyß, M. (2013). Fast Algorithm for Rank-Width. In: Kučera, A., Henzinger, T.A., Nešetřil, J., Vojnar, T., Antoš, D. (eds) Mathematical and Engineering Methods in Computer Science. MEMICS 2012. Lecture Notes in Computer Science, vol 7721. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-36046-6_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-36046-6_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-36044-2
Online ISBN: 978-3-642-36046-6
eBook Packages: Computer ScienceComputer Science (R0)