Monadic Second Order Logic on Graphs with Local Cardinality Constraints

DOI10.1007/978-3-540-85238-4_49MaRDI QIDQ3599161zbMATH OpenOpenAlexFDO

Authors Stefan Szeider

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85238-4_49

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Monadic second order logic on graphs with local cardinality constraints
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• scientific article; zbMATH DE number 4081531
• Easy problems for tree-decomposable graphs

Cites work

• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A partial k-arboretum of graphs with bounded treewidth
• Easy problems for tree-decomposable graphs
• Equitable Coloring
• General factors of graphs
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• scientific article; zbMATH DE number 1302199 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 3405992 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2004
• On Equitable Coloring of d-Degenerate Graphs
• On simple characterizations of k-trees
• Parametrized complexity theory.
• The factorization of graphs. II
• Tractable cases of the extended global cardinality constraint
• Treewidth. Computations and approximations

Cited in

(8)

• Local linear set on graphs with bounded twin cover number
• Monadic second order logic on graphs with local cardinality constraints
• scientific article; zbMATH DE number 1290983 (Why is no real title available?)
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• The complexity ecology of parameters: An illustration using bounded max leaf number
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• MSOL partitioning problems on graphs of bounded treewidth and clique-width

This page was built for publication: Monadic Second Order Logic on Graphs with Local Cardinality Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3599161)