article · ACM Transactions on Algorithms · 2008

Approximating rank-width and clique-width quickly

Cited by 131Abstract and details only

Abstract

Rank-width was defined by Oum and Seymour [2006] to investigate clique-width. They constructed an algorithm that either outputs a rank-decomposition of width at most f ( k ) for some function f or confirms that rank-width is larger than k in time O (| V | 9 log | V |) for an input graph G = ( V , E ) and a fixed k . We develop three separate algorithms of this kind with faster running time. We construct an O (| V | 4 )-time algorithm with f ( k ) = 3 k + 1 by constructing a subroutine for the previous algorithm; we avoid generic algorithms minimizing submodular functions used by Oum and Seymour. Another one is an O (| V | 3 )-time algorithm with f ( k ) = 24 k , achieved by giving a reduction from graphs to binary matroids; then we use an approximation algorithm for matroid branch-width by Hliněný [2005]. Finally we construct an O (| V | 3 )-time algorithm with f ( k ) = 3 k − 1 by combining the ideas of the two previously cited papers.

Cite this paper

APA 7

Oum, S. (2008). Approximating rank-width and clique-width quickly. ACM Transactions on Algorithms, 5(1), 1–20. https://doi.org/10.1145/1435375.1435385

MLA 9

Oum, Sang‐il. “Approximating rank-width and clique-width quickly.” ACM Transactions on Algorithms, vol. 5, no. 1, 2008, pp. 1–20, https://doi.org/10.1145/1435375.1435385.

Chicago

Oum, Sang‐il. 2008. “Approximating rank-width and clique-width quickly.” ACM Transactions on Algorithms 5 (1): 1–20. https://doi.org/10.1145/1435375.1435385.

Harvard

Oum, S. (2008) ‘Approximating rank-width and clique-width quickly’, ACM Transactions on Algorithms, 5(1), pp. 1–20. Available at: https://doi.org/10.1145/1435375.1435385.

BibTeX

@article{oum2008approximating,
  title = {{Approximating rank-width and clique-width quickly}},
  author = {Oum, Sang‐il},
  journal = {ACM Transactions on Algorithms},
  volume = {5},
  number = {1},
  pages = {1--20},
  year = {2008},
  doi = {10.1145/1435375.1435385}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.