Structural parameterizations of vertex integrity

DOI10.1016/J.TCS.2024.114954MaRDI QIDQ6652467zbMATH OpenFDO

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

Publication date 12 December 2024

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

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114954

zbMATH Keywords

parameterized complexitystructural graph parametervertex integrityvulnerability of graphs

Mathematics Subject Classification ID

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

Recommendations

• Structural parameterizations of vertex integrity (best paper)
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Measures of vulnerability–the integrity family
• Vertex-neighbor-integrity of composition graph \(P_m[G]\)
• Vertex-neighbor-integrity of composition graphs of paths

Cites work

• A survey of integrity
• Algorithmic meta-theorems for restrictions of treewidth
• Approximating clique-width and branch-width
• Approximating rank-width and clique-width quickly
• Bin packing with fixed number of bins revisited
• Cluster vertex deletion: a parameterization between vertex cover and clique-width
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Extended MSO model checking via small vertex integrity
• Face covers and the genus problem for apex graphs
• Finding Branch-Decompositions and Rank-Decompositions
• Fixed-parameter algorithms for cluster vertex deletion
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Fully polynomial-time algorithms parameterized by vertex integrity using fast matrix multiplication
• Fundamentals of parameterized complexity
• Graph Classes: A Survey
• scientific article; zbMATH DE number 4130410 (Why is no real title available?)
• scientific article; zbMATH DE number 4035869 (Why is no real title available?)
• scientific article; zbMATH DE number 4053662 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• scientific article; zbMATH DE number 7788607 (Why is no real title available?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• Measuring the vulnerability for classes of intersection graphs
• Modular decomposition and transitive orientation
• Parameterized algorithms
• Parameterized Algorithms for Modular-Width
• Parameterized complexity of safe set
• Parametrized complexity theory.
• Partitioning a graph into small pieces with applications to path transversal
• Safe number and integrity of graphs
• Safe sets in graphs: graph classes and structural parameters
• Some notes on bounded starwidth graphs
• The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints
• Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
• Vulnerability parameters of split graphs

Cited in

(4)

• Exploring the gap between treedepth and vertex cover through vertex integrity
• Structural parameterizations of vertex integrity (best paper)
• Combining crown structures for vulnerability measures
• Monotone bounded-depth complexity of homomorphism polynomials

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

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