Extended MSO model checking via small vertex integrity

DOI10.1007/s00453-023-01161-9arXiv2202.08445OpenAlexW4385667336MaRDI QIDQ6185940

Tatsuya Gima, Yota Otachi

Publication date: 9 January 2024

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

monadic second-order logicfixed-parameter tractabilitycardinality constraintvertex integrity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Safe set problem on graphs
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• On the complexity of some colorful problems parameterized by treewidth
• On the computational complexity of vertex integrity and component order connectivity
• An application of simultaneous diophantine approximation in combinatorial optimization
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• A partial k-arboretum of graphs with bounded treewidth
• Defensive alliances in graphs of bounded treewidth
• Safe number and integrity of graphs
• Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity
• Algorithmic meta-theorems for restrictions of treewidth
• The complexity of first-order and monadic second-order logic revisited
• Bin packing with fixed number of bins revisited
• Linear time solvable optimization problems on graphs of bounded clique-width
• Parameterized complexity of fair deletion problems
• On structural parameterizations of the bounded-degree vertex deletion problem
• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Expanding the Expressive Power of Monadic Second-Order Logic on Restricted Graph Classes
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• When Trees Grow Low: Shrubs and Fast MSO1
• Monadic second order logic on graphs with local cardinality constraints
• Integer Programming with a Fixed Number of Variables
• Easy problems for tree-decomposable graphs
• Capacitated Domination and Covering: A Parameterized Perspective
• Graph Layout Problems Parameterized by Vertex Cover
• What Makes Equitable Connected Partition Easy
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Minkowski's Convex Body Theorem and Integer Programming
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Parameterized (Approximate) Defective Coloring
• A survey on alliances and related parameters in graphs
• Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• Fair edge deletion problems
• Parameterized Algorithms
• Subgraph isomorphism on graph classes that exclude a substructure
• Exploring the gap between treedepth and vertex cover through vertex integrity
• An algorithmic framework for locally constrained homomorphisms

This page was built for publication: Extended MSO model checking via small vertex integrity