Approximating clique-width and branch-width
By Sang-il Oum, Paul D. Seymour. J. Comb. Theory B, 2006
549 citations recorded by the source corpus.
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics
View Paper: https://www.semanticscholar.org/paper/037492ca43d08a78bec226f658875ad169568885
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Discrete Mathematics and Combinatorics
Citations in the corpus
- On H-immersions (2008, unknown): “Oum and Seymour [8] showed that rwd(G) ≤ cwd(G) ≤ 2 − 1, where cwd(G), rwd(G) denote clique-width and rank-width respectively.”
- The n-ordered graphs: A new graph class (2009, methodology): “Oum and Seymour [18] defined rank-width of simple graphs as follows: rankwidth, rank-decomposition of a simple graph G is branch-width, branch-decomposition of ρG respectively.”
- Parameterized Complexity and Approximation Algorithms (2008, background): “However, standard fpt-approximation algorithms exist for these problems [96, 95, 68] One might be tempted to define the notion of standard fpt-approximation scheme to capture the situation where a problem has a standard fptapproximation algorithm for every c > 1.”
- Graphs of bounded rank-width (2005, unknown): “Seymour [43].”