Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width

By Bruno Courcelle, J. Makowsky, Udi Rotics. Theory of Computing Systems, 2000

791 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/5988c9ef001f08cb9da681f1d63abfb5a9f0f416

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

1. Daniel Marx
2. Saket Saurabh
3. Daniel Lokshtanov
4. Sang-il Oum
5. Paul D. Seymour

Citations in the corpus

• Lower bounds based on the Exponential Time Hypothesis (2011, background): “Several algorithms for NP-hard problems parameterized by these width measures have been obtained [17].”
• Approximating clique-width and branch-width (2006, background): “…whether the graph is Hamiltonian [23], finding the chromatic number [14], and various partition problems [8] are solvable in polynomial time; and so is any problem that can be expressed in monadic second order logic with quantifications over vertices and vertex sets (MSO 1 -logic; see [6] [5]).”
• Graphs of bounded rank-width (2005, neutral): “For example, cographs [10], graphs of clique-width at most 3 [9], and P4-sparse graphs (every five vertices have at most one induced subgraph isomorphic to a path of length 3) [18] have such algorithms.”