Name
Abstract | ||
|---|---|---|
We extend clique-width to graphs with multiple edges. We obtain fixed-parameter tractable model-checking algorithms for certain monadic second-order graph properties that depend on the multiplicities of edges, with respect to this ''new'' clique-width. We define special tree-width, the variant of tree-width relative to tree-decompositions such that the boxes that contain a vertex are on a path originating from some fixed node. We study its main properties. This definition is motivated by the construction of finite automata associated with monadic second-order formulas using edge set quantifications. These automata yield fixed-parameter linear algorithms with respect to tree-width for the model-checking of these formulas. Their construction is much simpler for special tree-width than for tree-width, for reasons that we explain. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.dam.2010.12.017 | Discrete Applied Mathematics |
Keywords | Field | DocType |
special tree-width,finite automaton,fixed-parameter tractable,graph decomposition,edge set quantifications,main property,model-checking,automata yield fixed-parameter,fixed node,certain monadic second-order graph,tree-width,clique-width,monadic second-order logic,monadic second-order formula,linear algorithm,clique width,model checking,tree width | Discrete mathematics,Combinatorics,Model checking,Graph property,Vertex (geometry),Finite-state machine,Treewidth,Clique-width,Multiple edges,Mathematics,Monadic predicate calculus | Journal |
Volume | Issue | ISSN |
160 | 6 | Discrete Applied Mathematics |
Citations | PageRank | References |
15 | 0.76 | 16 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bruno Courcelle | 1 | 3418 | 388.00 |