A dynamic data structure for MSO properties in graphs with bounded tree-depth

DOI10.1007/978-3-662-44777-2_28MaRDI QIDQ2921418zbMATH OpenOpenAlexFDO

Authors Zdeněk Dvořák, Martin Kupec, Vojtěch Tůma

Publication date 8 October 2014

Published in Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-44777-2_28

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Dynamic algorithms for graphs of bounded treewidth
• Dynamic algorithms for graphs of bounded treewidth
• Computing tree-depth faster than \(2^n\)
• When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)
• Testing first-order properties for subclasses of sparse graphs

Cited in

(10)

• Dynamic algorithms for graphs of bounded treewidth
• Symbolically Bounding the Drift in Time-Constrained MSC Graphs
• Dynamic algorithms for graphs of bounded treewidth
• A distributed low tree-depth decomposition algorithm for bounded expansion classes
• Decremental sensitivity oracles for covering and packing minors
• Maintaining \(\mathrm{CMSO}_2\) properties on dynamic structures with bounded feedback vertex number
• Dynamic coloring of unit interval graphs with limited recourse budget
• Parameterized dynamic data structure for split completion
• Dynamic parameterized feedback problems in tournaments
• Dynamic parameterized problems on unit disk graphs

This page was built for publication: A dynamic data structure for MSO properties in graphs with bounded tree-depth

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