scientific article; zbMATH DE number 1405654

MaRDI QIDQ4938635zbMATH OpenFDO

Authors Markus Frick, Martin Grohe

Publication date 23 February 2000

zbMATH Keywords

decidabilityfirst-order definable graph propertylinear time algorithmlocally tree-decomposable graphstree-width

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Deciding first-order properties of locally tree-decomposable structures
• scientific article; zbMATH DE number 2086422
• Generalized model-checking over locally tree-decomposable classes
• scientific article; zbMATH DE number 4081531
• Testing first-order properties for subclasses of sparse graphs

Cited in

(11)

• Analysis and application of adaptive sampling
• On the parameterized complexity of the expected coverage problem
• Parameterized counting problems
• Deciding first-order properties of locally tree-decomposable structures
• Confronting intractability via parameters
• scientific article; zbMATH DE number 2086422 (Why is no real title available?)
• On the Parameterized Complexity of the Expected Coverage Problem
• Data-compression for parametrized counting problems on sparse graphs
• Generalized model-checking over locally tree-decomposable classes
• Twin-width of graphs on surfaces
• Compactors for parameterized counting problems

This page was built for publication:

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