On the computational complexity of vertex integrity and component order connectivity (Q727981): Difference between revisions

Latest revision as of 04:25, 13 July 2024

scientific article; zbMATH DE number 6480921

On the Computational Complexity of Vertex Integrity and Component Order Connectivity

Language	Label	Description	Also known as
English	On the computational complexity of vertex integrity and component order connectivity	scientific article; zbMATH DE number 6480921	On the Computational Complexity of Vertex Integrity and Component Order Connectivity

Statements

instance of

scholarly article

0 references

title

On the computational complexity of vertex integrity and component order connectivity (English)

0 references

On the Computational Complexity of Vertex Integrity and Component Order Connectivity (English)

0 references

author

D. Kharzeev

0 references

Pål Grønås Drange

0 references

Markus Sortland Dregi

0 references

Pim van 't Hof

0 references

published in

Algorithmica

0 references

Algorithms and Computation

0 references

publication date

21 December 2016

0 references

11 September 2015

0 references

full work available at URL

https://arxiv.org/abs/1403.6331

0 references

zbMATH Keywords

graph vulnerability

0 references

parameterized complexity

0 references

complexity

0 references

graph algorithms

0 references

preprocessing

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

A survey of integrity

0 references

Q3789603

0 references

The k-Separator Problem

0 references

Equitable colorings of bounded treewidth graphs

0 references

Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

0 references

Q3775581

0 references

On the computational complexity of vertex integrity and component order connectivity

0 references

Q3032280

0 references

Q4198056

0 references

Counting clique trees and computing perfect elimination schemes in parallel

0 references

Measuring the vulnerability for classes of intersection graphs

0 references

Vulnerability parameters of split graphs

0 references

Q4320674

0 references

Q3428636

0 references

The toughness of split graphs

0 references

Graph Classes: A Survey

0 references

A partial k-arboretum of graphs with bounded treewidth

0 references

Q4393480

0 references

Q5315023

0 references

Comparability graphs and intersection graphs

0 references

The clique-separator graph for chordal graphs

0 references

On the complexity of \(k\)-SAT

0 references

Which problems have strongly exponential complexity?

0 references

Q5365079

0 references

Identifiers

zbMATH Open document ID

1355.68115

0 references

1352.68103

0 references

DOI

10.1007/s00453-016-0127-x

0 references

10.1007/978-3-319-13075-0_23

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:727981

@@ Property / cites work @@
+Graph Classes: A Survey
@@ Property / cites work: Graph Classes: A Survey / rank @@
+Normal rank
@@ Property / cites work @@
+A partial k-arboretum of graphs with bounded treewidth
+Normal rank
@@ Property / cites work @@
+Q4393480
@@ Property / cites work: Q4393480 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5315023
@@ Property / cites work: Q5315023 / rank @@
+Normal rank
@@ Property / cites work @@
+Comparability graphs and intersection graphs
@@ Property / cites work: Comparability graphs and intersection graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The clique-separator graph for chordal graphs
@@ Property / cites work: The clique-separator graph for chordal graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of \(k\)-SAT
@@ Property / cites work: On the complexity of \(k\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+Q5365079
@@ Property / cites work: Q5365079 / rank @@
+Normal rank