On the computational complexity of vertex integrity and component order connectivity

DOI10.1007/s00453-016-0127-xzbMath1355.68115arXiv1403.6331OpenAlexW2460257212MaRDI QIDQ727981

D. Kharzeev, Pål Grønås Drange, Markus Sortland Dregi, Pim van 't Hof

Publication date: 21 December 2016

Published in: Algorithmica, Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

complexitygraph algorithmsparameterized complexitypreprocessinggraph vulnerability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (31)

Linear kernels for separating a graph into components of bounded size ⋮ Deleting edges to restrict the size of an epidemic: a new application for treewidth ⋮ Network Elicitation in Adversarial Environment ⋮ Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property ⋮ Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth ⋮ Component order connectivity in directed graphs ⋮ The vertex attack tolerance of complex networks ⋮ An algorithmic framework for locally constrained homomorphisms ⋮ Parameterized complexity of multicut in weighted trees ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Extended MSO model checking via small vertex integrity ⋮ Parameterized Complexity of Safe Set ⋮ Assigning times to minimise reachability in temporal graphs ⋮ Faster parameterized algorithms for two vertex deletion problems ⋮ Unnamed Item ⋮ The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints ⋮ Network majority on tree topological network ⋮ The critical node detection problem in networks: a survey ⋮ Parameterized complexity of critical node cuts ⋮ Slightly Superexponential Parameterized Problems ⋮ Component order connectivity in directed graphs ⋮ Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ On the computational complexity of vertex integrity and component order connectivity ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Unnamed Item ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ Exploring the gap between treedepth and vertex cover through vertex integrity ⋮ Parameterized algorithms for generalizations of directed feedback vertex set ⋮ Partitioning a graph into small pieces with applications to path transversal ⋮ Unnamed Item

Cites Work

• On the computational complexity of vertex integrity and component order connectivity
• Equitable colorings of bounded treewidth graphs
• The clique-separator graph for chordal graphs
• Comparability graphs and intersection graphs
• A survey of integrity
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Counting clique trees and computing perfect elimination schemes in parallel
• A partial k-arboretum of graphs with bounded treewidth
• Measuring the vulnerability for classes of intersection graphs
• The toughness of split graphs
• Which problems have strongly exponential complexity?
• Graph Classes: A Survey
• The k-Separator Problem
• Vulnerability parameters of split graphs
• On the complexity of \(k\)-SAT
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the computational complexity of vertex integrity and component order connectivity