Optimal Algorithm of Isolated Toughness for Interval Graphs

Fengwei Li; Qingfang Ye; Hajo Broersma; Xiaoyan Zhang

doi:10.1007/978-3-030-69244-5_34

Optimal Algorithm of Isolated Toughness for Interval Graphs

Fengwei Li, Qingfang Ye, Hajo Broersma, Xiaoyan Zhang^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Downloads (Pure)

Abstract

Factor and fractional factor are widely used in many fields related to computer science. The isolated toughness of an incomplete graph G is defined as iτ(G)=min{|S|i(G-S):S∈C(G),i(G-S)>1}. Otherwise, we set iτ(G) = ∞ if G is complete. This parameter has a close relationship with the existence of factors and fractional factors of graphs. In this paper, we pay our attention to computational complexity of isolated toughness, and present an optimal polynomial time algorithm to compute the isolated toughness for interval graphs, a subclass of co-comparability graphs.

Original language	English
Title of host publication	Parallel and Distributed Computing, Applications and Technologies
Subtitle of host publication	21st International Conference, PDCAT 2020, Shenzhen, China, December 28–30, 2020, Proceedings
Editors	Yong Zhang, Yicheng Xu, Hui Tian
Place of Publication	Cham
Publisher	Springer
Pages	379-388
Number of pages	10
ISBN (Electronic)	978-3-030-69244-5
ISBN (Print)	978-3-030-69243-8
DOIs	https://doi.org/10.1007/978-3-030-69244-5_34
Publication status	Published - 21 Feb 2021
Event	21st International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2020 - Virtual Conference, Shenzhen, China Duration: 28 Dec 2020 → 30 Dec 2020 Conference number: 21

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12606
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2020
Abbreviated title	PDCAT 2020
Country/Territory	China
City	Shenzhen
Period	28/12/20 → 30/12/20

Keywords

Factor
Fractional factor
Interval graph
Isolated toughness
Polynomial time algorithm

Access to Document

10.1007/978-3-030-69244-5_34

Li-2021-OptimalFinal published version, 264 KBLicence: Taverne

Cite this

Li, F., Ye, Q., Broersma, H., & Zhang, X. (2021). Optimal Algorithm of Isolated Toughness for Interval Graphs. In Y. Zhang, Y. Xu, & H. Tian (Eds.), Parallel and Distributed Computing, Applications and Technologies: 21st International Conference, PDCAT 2020, Shenzhen, China, December 28–30, 2020, Proceedings (pp. 379-388). (Lecture Notes in Computer Science; Vol. 12606). Springer. https://doi.org/10.1007/978-3-030-69244-5_34

Li, Fengwei ; Ye, Qingfang ; Broersma, Hajo et al. / Optimal Algorithm of Isolated Toughness for Interval Graphs. Parallel and Distributed Computing, Applications and Technologies: 21st International Conference, PDCAT 2020, Shenzhen, China, December 28–30, 2020, Proceedings. editor / Yong Zhang ; Yicheng Xu ; Hui Tian. Cham : Springer, 2021. pp. 379-388 (Lecture Notes in Computer Science).

@inproceedings{eb5681eed97f4925aad3a0c83cb73d48,

title = "Optimal Algorithm of Isolated Toughness for Interval Graphs",

abstract = "Factor and fractional factor are widely used in many fields related to computer science. The isolated toughness of an incomplete graph G is defined as iτ(G)=min{|S|i(G-S):S∈C(G),i(G-S)>1}. Otherwise, we set iτ(G) = ∞ if G is complete. This parameter has a close relationship with the existence of factors and fractional factors of graphs. In this paper, we pay our attention to computational complexity of isolated toughness, and present an optimal polynomial time algorithm to compute the isolated toughness for interval graphs, a subclass of co-comparability graphs.",

keywords = "Factor, Fractional factor, Interval graph, Isolated toughness, Polynomial time algorithm",

author = "Fengwei Li and Qingfang Ye and Hajo Broersma and Xiaoyan Zhang",

note = "Funding Information: Acknowledgements. This work was supported by NSFC (No.11871280), Natural Science Foundation of Zhejiang Province(China) (No. LY17A010017) and Qing Lan Project. Especially, the authors are very thankful to anonymous referees for their constructive suggestions and critical comments, which led to this improved version. Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 21st International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2020, PDCAT 2020 ; Conference date: 28-12-2020 Through 30-12-2020",

year = "2021",

month = feb,

day = "21",

doi = "10.1007/978-3-030-69244-5_34",

language = "English",

isbn = "978-3-030-69243-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "379--388",

editor = "Yong Zhang and Yicheng Xu and Hui Tian",

booktitle = "Parallel and Distributed Computing, Applications and Technologies",

}

Li, F, Ye, Q, Broersma, H & Zhang, X 2021, Optimal Algorithm of Isolated Toughness for Interval Graphs. in Y Zhang, Y Xu & H Tian (eds), Parallel and Distributed Computing, Applications and Technologies: 21st International Conference, PDCAT 2020, Shenzhen, China, December 28–30, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12606, Springer, Cham, pp. 379-388, 21st International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2020, Shenzhen, China, 28/12/20. https://doi.org/10.1007/978-3-030-69244-5_34

Optimal Algorithm of Isolated Toughness for Interval Graphs. / Li, Fengwei; Ye, Qingfang; Broersma, Hajo et al.

Parallel and Distributed Computing, Applications and Technologies: 21st International Conference, PDCAT 2020, Shenzhen, China, December 28–30, 2020, Proceedings. ed. / Yong Zhang; Yicheng Xu; Hui Tian. Cham : Springer, 2021. p. 379-388 (Lecture Notes in Computer Science; Vol. 12606).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Optimal Algorithm of Isolated Toughness for Interval Graphs

AU - Li, Fengwei

AU - Ye, Qingfang

AU - Broersma, Hajo

AU - Zhang, Xiaoyan

N1 - Conference code: 21

PY - 2021/2/21

Y1 - 2021/2/21

N2 - Factor and fractional factor are widely used in many fields related to computer science. The isolated toughness of an incomplete graph G is defined as iτ(G)=min{|S|i(G-S):S∈C(G),i(G-S)>1}. Otherwise, we set iτ(G) = ∞ if G is complete. This parameter has a close relationship with the existence of factors and fractional factors of graphs. In this paper, we pay our attention to computational complexity of isolated toughness, and present an optimal polynomial time algorithm to compute the isolated toughness for interval graphs, a subclass of co-comparability graphs.

AB - Factor and fractional factor are widely used in many fields related to computer science. The isolated toughness of an incomplete graph G is defined as iτ(G)=min{|S|i(G-S):S∈C(G),i(G-S)>1}. Otherwise, we set iτ(G) = ∞ if G is complete. This parameter has a close relationship with the existence of factors and fractional factors of graphs. In this paper, we pay our attention to computational complexity of isolated toughness, and present an optimal polynomial time algorithm to compute the isolated toughness for interval graphs, a subclass of co-comparability graphs.

KW - Factor

KW - Fractional factor

KW - Interval graph

KW - Isolated toughness

KW - Polynomial time algorithm

UR - http://www.scopus.com/inward/record.url?scp=85104382161&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-69244-5_34

DO - 10.1007/978-3-030-69244-5_34

M3 - Conference contribution

AN - SCOPUS:85104382161

SN - 978-3-030-69243-8

T3 - Lecture Notes in Computer Science

SP - 379

EP - 388

BT - Parallel and Distributed Computing, Applications and Technologies

A2 - Zhang, Yong

A2 - Xu, Yicheng

A2 - Tian, Hui

PB - Springer

CY - Cham

T2 - 21st International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2020

Y2 - 28 December 2020 through 30 December 2020

ER -

Li F, Ye Q, Broersma H, Zhang X. Optimal Algorithm of Isolated Toughness for Interval Graphs. In Zhang Y, Xu Y, Tian H, editors, Parallel and Distributed Computing, Applications and Technologies: 21st International Conference, PDCAT 2020, Shenzhen, China, December 28–30, 2020, Proceedings. Cham: Springer. 2021. p. 379-388. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-69244-5_34

Optimal Algorithm of Isolated Toughness for Interval Graphs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this