Capturing polynomial time using modular decomposition

MaRDI QIDQ3121526zbMATH OpenFDO

Authors Berit Grußien

Publication date 18 March 2019

Full work available at URL https://arxiv.org/abs/1803.11134

zbMATH Keywords

descriptive complexityfixed-point logic with countinggraph canonizationgraph coloringsgraph isomorphismlogarithmic spacemodular decompositionpermutation graphspolynomial timesymmetric transitive closure logictransduction

Mathematics Subject Classification ID

Logic in computer science (03B70) Model theory of finite structures (03C13) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Capturing polynomial time using modular decomposition
• A survey of the algorithmic aspects of modular decomposition
• The modular decomposition of countable graphs. Definition and construction in monadic second-order logic
• Incremental modular decomposition
• Algorithmic aspects of a general modular decomposition theory

Cited in

(3)

• Fixed-point definability and polynomial time on chordal graphs and line graphs
• Capturing polynomial time using modular decomposition
• A proof system for graph (non)-isomorphism verification

This page was built for publication: Capturing polynomial time using modular decomposition

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