Measuring the vulnerability for classes of intersection graphs

DOI10.1016/S0166-218X(96)00133-3zbMath0881.05118OpenAlexW2012676186MaRDI QIDQ1364473

Ton Kloks, Dieter Kratsch, Haiko Müller

Publication date: 16 February 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

measuresvulnerabilitytrapezoid graphsintersection graphspolynomial time algorithmsscattering numberbinding numberminimum balanced separator problemthoughnessvertex integrity

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Vertex ranking of asteroidal triple-free graphs ⋮ The scattering number of strictly chordal graphs: linear time determination ⋮ The scattering number of thorn graphs ⋮ Characterization of interval graphs that are unpaired 2-disjoint path coverable ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ Toughness and Hamiltonicity of strictly chordal graphs ⋮ Fission: Practical algorithms for computing minimum balanced node separators ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Computational complexity of network vulnerability analysis ⋮ Parameterized Complexity of Safe Set ⋮ Network robustness and residual closeness ⋮ A Note on the Link Residual Closeness of Graphs Under Join Operation ⋮ Link Vulnerability in Networks ⋮ Vulnerability of subclasses of chordal graphs ⋮ 2-edge-Hamiltonian-connectedness of 4-connected plane graphs ⋮ On the computational complexity of vertex integrity and component order connectivity ⋮ The Valve Location Problem in Simple Network Topologies ⋮ Unnamed Item ⋮ Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs

Cites Work

• Trapezoid graphs and generalizations, geometry and algorithms
• Recognizing tough graphs is NP-hard
• Trapezoid graphs and their coloring
• On a class of posets and the corresponding comparability graphs
• Toughness and matching extension in graphs
• Tough graphs and Hamiltonian circuits.
• Applications of a Planar Separator Theorem
• Treewidth and Pathwidth of Permutation Graphs
• The binding number of a graph and its Anderson number
• Research problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item