On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic (Q5928867)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1584464
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic |
scientific article; zbMATH DE number 1584464 |
Statements
On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic (English)
0 references
9 November 2001
0 references
This paper considers counting and evaluation problems on graphs, where the range of counting is definable in monadic second-order logic. In this paper, the graphs are restricted to those with some upper bound on the treewidth. Problems that are otherwise computationally intractable become polynomial time solvable with this restriction. Similar results are given when the clique width is bounded, but now we must have in addition some algorithm that finds appropriate clique decompositions, and no edge set quantification is allowed in the monadic second-order logic formulas. Several applications of the theory are discussed.
0 references
fixed parameter complexity
0 references
combinatorial enumeration
0 references
treewidth
0 references
monadic second-order logic
0 references
0.9191142
0 references
0.9140268
0 references
0.91186064
0 references
0.91186064
0 references
0.91172755
0 references
0.91144794
0 references
0.9107748
0 references
0.90994966
0 references
