Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Approximating rank-width and clique-width quickly

Approximating rank-width and clique-width quickly Approximating Rank-Width and Clique-Width Quickly SANG-IL OUM KAIST Abstract. Rank-width was de ned 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 con rms that rank-width is larger than k in time O(|V |9 log |V |) for an input graph G = (V, E) and a xed k. We develop three separate algorithms of this kind with faster running time. We construct an O(|V |4 )-time algorithm with f (k) = 3k + 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) = 24k, 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) = 3k ’ 1 by combining e y the ideas of the two previously cited papers. Categories and Subject Descriptors: G.2.2 [Discrete Mathematics]: Graph Theory ”Graph algorithms General Terms: Algorithms, Theory Additional Key Words and Phrases: Approximation http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Approximating rank-width and clique-width quickly

Oum, Sang-Il
ACM Transactions on Algorithms (TALG) , Volume 5 (1) – Nov 1, 2008
Download PDF
20 pages

Loading next page...
 
/lp/association-for-computing-machinery/approximating-rank-width-and-clique-width-quickly-02cRS5jGHP
Publisher
Association for Computing Machinery
Copyright
Copyright © 2008 by ACM Inc.
ISSN
1549-6325
DOI
10.1145/1435375.1435385
Publisher site
See Article on Publisher Site

Abstract

Approximating Rank-Width and Clique-Width Quickly SANG-IL OUM KAIST Abstract. Rank-width was de ned 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 con rms that rank-width is larger than k in time O(|V |9 log |V |) for an input graph G = (V, E) and a xed k. We develop three separate algorithms of this kind with faster running time. We construct an O(|V |4 )-time algorithm with f (k) = 3k + 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) = 24k, 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) = 3k ’ 1 by combining e y the ideas of the two previously cited papers. Categories and Subject Descriptors: G.2.2 [Discrete Mathematics]: Graph Theory ”Graph algorithms General Terms: Algorithms, Theory Additional Key Words and Phrases: Approximation

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Nov 1, 2008

There are no references for this article.