A polynomial algorithm for weighted scattering number in interval graphs

DOI10.1016/j.dam.2019.01.004zbMath1414.05276OpenAlexW2912539891WikidataQ128360668 ScholiaQ128360668MaRDI QIDQ2422741

Fengwei Li, Xiaoyan Zhang, Hajo J. Broersma

Publication date: 20 June 2019

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

Full work available at URL: https://doi.org/10.1016/j.dam.2019.01.004

zbMATH Keywords

interval graphtoughnessscattering numbernetwork vulnerabilitylocal cutweighted scattering number

Mathematics Subject Classification ID

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

Related Items

The scattering number of strictly chordal graphs: linear time determination, Computing the weighted neighbor isolated tenacity of interval graphs in polynomial time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognizing tough graphs is NP-hard
• Geometric algorithms and combinatorial optimization
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On a class of posets and the corresponding comparability graphs
• Scattering number and modular decomposition
• Tough graphs and Hamiltonian circuits.
• Scattering number in graphs
• One-dimensional logic gate assignment and interval graphs
• Computing the Scattering Number of Graphs
• Relationships between scattering number and other vulnerability parameters
• Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs
• A Characterization of Comparability Graphs and of Interval Graphs