Structural parameterizations of vertex integrity

DOI10.1016/j.tcs.2024.114954MaRDI QIDQ6652467

Tatsuya Gima, Yota Otachi, Tesshu Hanaka, Yasuaki Kobayashi, Ryota Murai, Hirotaka Ono

Publication date: 12 December 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

parameterized complexityvertex integritystructural graph parametervulnerability of graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• On the computational complexity of vertex integrity and component order connectivity
• Fixed-parameter algorithms for cluster vertex deletion
• A survey of integrity
• Modular decomposition and transitive orientation
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Measuring the vulnerability for classes of intersection graphs
• Safe sets in graphs: graph classes and structural parameters
• Safe number and integrity of graphs
• Algorithmic meta-theorems for restrictions of treewidth
• Face covers and the genus problem for apex graphs
• Bin packing with fixed number of bins revisited
• Linear time solvable optimization problems on graphs of bounded clique-width
• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• Partitioning a graph into small pieces with applications to path transversal
• Parametrized complexity theory.
• Approximating clique-width and branch-width
• Some notes on bounded starwidth graphs
• Parameterized Algorithms for Modular-Width
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
• Graph Classes: A Survey
• Approximating rank-width and clique-width quickly
• Parameterized Complexity of Safe Set
• Vulnerability parameters of split graphs
• Parameterized Algorithms
• Finding Branch-Decompositions and Rank-Decompositions
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Extended MSO model checking via small vertex integrity
• Fully polynomial-time algorithms parameterized by vertex integrity using fast matrix multiplication

This page was built for publication: Structural parameterizations of vertex integrity