A polynomial algorithm for weighted scattering number in interval graphs
From MaRDI portal
Publication:2422741
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
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