Open AccessA Polynomial Algorithm for Weighted Toughness of Interval Graphs
Author(s) -
Ming Shi,
Zongtian Wei
Publication year - 2021
Publication title -
journal of mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.252
H-Index - 13
eISSN - 2314-4785
pISSN - 2314-4629
DOI - 10.1155/2021/6657594
Subject(s) - mathematics , toughness , interval (graph theory) , interval graph , combinatorics , algorithm , polynomial , discrete mathematics , graph , chordal graph , 1 planar graph , mathematical analysis , composite material , materials science
The concept of toughness, introduced by Chv a ´ tal, has been widely used as an important invulnerability parameter. This parameter is generalized to weighted graphs, and the concept of weighted toughness is proposed. A polynomial algorithm for computing the weighted toughness of interval graphs is given.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom