On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width

Robert Ganian, Petr HlinenýDiscret. Appl. Math 2010 · DOI · OpenReview

Abstract

Rank-width is a structural graph measure introduced by Oum and Seymour and aimed at better handling of graphs of bounded clique-width. We propose a formal mathematical framework and tools for easy design of dynamic algorithms running directly on a rank-decomposition of a graph (on contrary to the usual approach which translates a rank-decomposition into a clique-width expression, with a possible exponential jump in the parameter). The main advantage of this framework is a fine control over the runtime dependency on the rank-width parameter. Our new approach is linked to a work of Courcelle and Kanté [7] who first proposed algebraic expressions with a so-called bilinear graph product as a better way of handling rank-decompositions, and to a parallel recent research of Bui-Xuan, Telle and Vatshelle.
BibTeX
@article{ganian2010parse,
  author = {Robert Ganian and Petr Hlinený},
  title = {{On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width}},
  journal = {Discret. Appl. Math.},
  year = {2010},
  doi = {10.1016/j.dam.2009.10.018},
}

Loading related content...

Figure