摘要: Inspired by the heuristic algorithm for boolean-width Telle et. al. [1], we develop a rank-width. We compare results on graphs of practical relevance to established bounds boolean-width. While width most is lower than known values tree-width, it turns out that able find decompositions significantly width. In second step therefore present further can decide if graph G and value k exists rank-decomposition k. This enables show in fact or equal rank-width many investigated graphs.
springer.com
sci-hub.st 参考文章(18)
Eivind Magnus Hvidevold, Sadia Sharmin, Jan Arne Telle, Martin Vatshelle, Finding good decompositions for dynamic programming on dense graphs international symposium on parameterized and exact computation. pp. 219- 231 ,(2011) , 10.1007/978-3-642-28050-4_18
Michael A. Trick, David J. Johnson, Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993 American Mathematical Society. ,(1996)
Donald E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing ,(1993)
Neil Robertson, P.D Seymour, Graph minors. III. Planar tree-width Journal of Combinatorial Theory, Series B. ,vol. 36, pp. 49- 64 ,(1984) , 10.1016/0095-8956(84)90013-3
Bruno Courcelle, The monadic second-order logic of graphs. I. recognizable sets of finite graphs Information & Computation. ,vol. 85, pp. 12- 75 ,(1990) , 10.1016/0890-5401(90)90043-H
Eric Torng, Jason McCullough, SRPT optimally utilizes faster machines to minimize flow time ACM Transactions on Algorithms. ,vol. 5, pp. 1- 25 ,(2008) , 10.1145/1435375.1435376
P. Hlineny, S.-i. Oum, D. Seese, G. Gottlob, Width Parameters Beyond Tree-width and their Applications The Computer Journal. ,vol. 51, pp. 326- 362 ,(2008) , 10.1093/COMJNL/BXM052
P.D Seymour, Neil Robertson, Graph minors: X. obstructions to tree-decomposition Journal of Combinatorial Theory, Series B. ,vol. 52, pp. 153- 190 ,(1991) , 10.1016/0095-8956(91)90061-N
B. Courcelle, J. A. Makowsky, U. Rotics, Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width Theory of Computing Systems \/ Mathematical Systems Theory. ,vol. 33, pp. 125- 150 ,(2000) , 10.1007/S002249910009
Sang-il Oum, Paul Seymour, Approximating clique-width and branch-width Journal of Combinatorial Theory, Series B. ,vol. 96, pp. 514- 528 ,(2006) , 10.1016/J.JCTB.2005.10.006