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 proceedingConference contributionAcademicpeer-review

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 languageEnglish
Title of host publicationParallel and Distributed Computing, Applications and Technologies - 21st International Conference, PDCAT 2020, Proceedings
EditorsYong Zhang, Yicheng Xu, Hui Tian
PublisherSpringer Science + Business Media
Pages379-388
Number of pages10
ISBN (Print)9783030692438
DOIs
Publication statusPublished - 2021
Event21st International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2020 - Virtual Conference, Shenzhen, China
Duration: 28 Dec 202030 Dec 2020
Conference number: 21

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12606 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st International Conference on Parallel and Distributed Computing, Applications, and Technologies, PDCAT 2020
Abbreviated titlePDCAT 2020
Country/TerritoryChina
CityShenzhen
Period28/12/2030/12/20

Keywords

  • Factor
  • Fractional factor
  • Interval graph
  • Isolated toughness
  • Polynomial time algorithm

Fingerprint

Dive into the research topics of 'Optimal Algorithm of Isolated Toughness for Interval Graphs'. Together they form a unique fingerprint.

Cite this