The neighbour-scattering number can be computed in polynomial time for interval graphs

DOI10.1016/J.CAMWA.2007.02.006MaRDI QIDQ1005803zbMATH OpenOpenAlexFDO

Authors Fengwei Li, Xueliang Li

Publication date 10 March 2009

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

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

zbMATH Keywords

consecutive clique arrangementinterval graphneighbour-scattering number

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Neighbor-scattering number is a useful measure for graph vulnerability. For some special kinds of graphs, explicit formulas are given for this number. However, for general graphs it is shown that to compute this number is NP-complete. In this paper, we prove that for interval graphs this number can be computed in polynomial time.

Recommendations

• Computing the weighted isolated scattering number of interval graphs in polynomial time
• A polynomial algorithm for weighted scattering number in interval graphs
• Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
• Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
• Vulnerability parameters of split graphs

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• Graph theory
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4031742 (Why is no real title available?)
• scientific article; zbMATH DE number 3628999 (Why is no real title available?)
• Incidence matrices and interval graphs
• On Maximal Circuits in Finite Graphs
• Optimal K-secure graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(6)

• Computing the weighted isolated scattering number of interval graphs in polynomial time
• A polynomial algorithm for weighted scattering number in interval graphs
• Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
• Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
• Computing the weighted neighbor isolated tenacity of interval graphs in polynomial time
• Isolated scattering number can be computed in polynomial time for interval graphs

This page was built for publication: The neighbour-scattering number can be computed in polynomial time for interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1005803)