On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
Copyright policy )On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
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.
- Université de Bordeaux France
- UNIVERSITE BORDEAUX 2 France
- University of Bordeaux France
- UNIVERSITE DE BORDEAUX 1 France
- Universite de Bordeaux France
combinatorial enumeration, Applied Mathematics, monadic second-order logic, Enumeration in graph theory, Fixed parameter complexity, Graph algorithms (graph-theoretic aspects), treewidth, Discrete Mathematics and Combinatorics, Combinatorial enumeration, fixed parameter complexity, Higher-order logic; type theory
combinatorial enumeration, Applied Mathematics, monadic second-order logic, Enumeration in graph theory, Fixed parameter complexity, Graph algorithms (graph-theoretic aspects), treewidth, Discrete Mathematics and Combinatorics, Combinatorial enumeration, fixed parameter complexity, Higher-order logic; type theory
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).120 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 1% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!