Combining crown structures for vulnerability measures

DOI10.1007/S00453-025-01348-2MaRDI QIDQ6894521zbMATH OpenFDO

Authors Katrin Casel, Tobias Friedrich, Kirill Simonov

Publication date 25 November 2025

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-025-01348-2

zbMATH Keywords

component-order connectivitycrown decompositionkernelizationvertex integrity

Mathematics Subject Classification ID

Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A 2k-kernelization algorithm for vertex cover based on crown decomposition
• A \(5k\)-vertex kernel for 3-path vertex cover
• A survey of integrity
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Extended MSO model checking via small vertex integrity
• Fine-grained meta-theorems for vertex integrity
• Fixed parameter multi-objective evolutionary algorithms for the W-separator problem
• Fully polynomial-time algorithms parameterized by vertex integrity using fast matrix multiplication
• 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 6857816 (Why is no real title available?)
• scientific article; zbMATH DE number 7740881 (Why is no real title available?)
• scientific article; zbMATH DE number 7768372 (Why is no real title available?)
• Kernelization. Theory of parameterized preprocessing
• Kernels for packing and covering problems
• Linear kernels for separating a graph into components of bounded size
• Measuring the vulnerability for classes of intersection graphs
• On maximal independent sets of vertices in claw-free graphs
• On structural parameterizations of the edge disjoint paths problem
• On the computational complexity of vertex integrity and component order connectivity
• Partitioning a graph into small pieces with applications to path transversal
• Structural parameterizations of vertex integrity
• Vulnerability parameters of split graphs

This page was built for publication: Combining crown structures for vulnerability measures

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