Publication details
Automata formalization for graphs of bounded rank-width
| Authors | |
|---|---|
| Year of publication | 2008 |
| Type | Conference abstract |
| MU Faculty or unit | |
| Citation | |
| Description | Rank-width is a brand new theoretical property of graphs, introduced by Oum and Seymour. The notion originated as a tool to better deal with graphs of bounded clique-width, yet rank-width is a completely selfcontained, stand-alone property of graphs. It is natural to ask whether we can use the fact that a given class of graphs has bounded rank-width to design more efficient algorithms for this specific class of graphs. There have been successful works which have shown that it is possible to use so-called parse trees to generate graphs of bounded tree-width and matroids of bounded branch-width, the general idea being that there exist many standardized tools for designing algorithms for parse trees. It should be noted that a graph has bounded rank-width if and only if it has bounded clique-width. However, the rank-width of a graph can be much smaller (even exponentially) than its clique-width, so designing algorithms through this new approach may lead to exponentially better results for a given class of graphs. We first introduce our labeling formalism used for representing bipartite adjacency matrices of graphs, followed by a definition of parse trees for graphs of bounded rank-width. The next chapter of the work contains our proof of an analogue to the Myhill-Nerode theorem for our notion of parse trees for graphs of bounded rank-width. |