Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Blood Leukocyte Object Detection According to Model Parameter-Transfer and Deformable Convolution Read chapter Read first chapter

2021 | OriginalPaper | Chapter

Optimal Algorithm of Isolated Toughness for Interval Graphs

Authors : Fengwei Li, Qingfang Ye, Hajo Broersma, Xiaoyan Zhang

Published in: Parallel and Distributed Computing, Applications and Technologies

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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\tau (G)=\min \{\frac{|S|}{i(G-S)}:S\in C(G), i(G-S)>1\}\). Otherwise, we set \(i\tau (G)=\infty \) 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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter The Prize-Collecting k-Steiner Tree Problem
next chapter Graceful Performance Degradation in Apache Storm
Literature
1.
Bondy, J., Murty, U.: Graph Theory with Applications. Macmillan, London and Elsevier, New york (1976)
2.
Booth, K., Lueker, G.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. System Sci. 13(3), 335–379 (1976)MathSciNetCrossRef
3.
Broersma, H., Fiala, J., Golovach, P., Kaiser, T., Paulusma, D., Proskurowski, A.: Linear-time algorithms for scattering number and hamilton-connectivity of interval graphs. J. Graph Theor. 79(4), 282–299 (2015)MathSciNetCrossRef
4.
5.
6.
Enomoto, H., Jackson, B., Katerinis, P., Saito, A.: Toughness and the existence of \(k\)-factors. J. Graph Theor. 9, 87–95 (1985)MathSciNetCrossRef
7.
Fabri, J.: Automatic Storage Optimization. UMI Press Ann Arbor, MI (1982)
8.
Gilmore, P., Hoffman, A.: A characterization of comparability graphs and of interval graphs. Can. J. Math. 16(99), 539–548 (1964)MathSciNetCrossRef
9.
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press (1980)
10.
Jungck, J., Dick, O., Dick, A.: Computer assisted sequencing, interval graphs and molecular evolution. Biosystem 15, 259–273 (1982)CrossRef
11.
12.
Kloks, A.J.J., Kratsch, D., Spinrad, J.P.: Treewidth and pathwidth of co comparability graphs of bounded dimension. Computing Science Note. Eindhoven University of Technology, Eindhoven, The Netherlands 9346 (1993)
13.
Kratsch, D., Klocks, T., Müller, H.: Computing the toughness and the scattering number for interval and other graphs. IRISA resarch report. France (1994)
14.
Li, F., LI, X.: Neighbor-scattering number can be computed in polynomial time for interval graphs. Comput. Math. Appl. 54(5), 679–686 (2007)MathSciNetCrossRef
15.
Ma, Y., Liu, G.: Isolated toughness and the existence of fractional factors in graphs. Acta Appl. Math. Sinica (in Chinese) 62, 133–140 (2003)MATH
16.
Ma, Y., Liu, G.: Fractional factors and isolated toughness of graphs. Mathematica Applicata 19(1), 188–194 (2006)MathSciNetMATH
17.
Ma, Y., Wang, A., Li, J.: Isolated toughness and fractional \((g, f)\)-factors of graphs. Ars Comb. 93, 153–160 (2009)MathSciNetMATH
18.
19.
Ma, Y., Yu, Q.: Isolated toughness and existence of \([a, b]\)-factors in graphs. J. Combin. Math. Combin. Comput. 62, 1–12 (2007)MathSciNetMATH
20.
Ohtsuki, T., Mori, H., Khu, E., Kashiwabara, T., Fujisawa, T.: One dimensional logic gate assignment and interval graph. IEEE Trans. Circ. Syst. 26, 675–684 (1979)MathSciNetCrossRef
21.
Scheinerman, E.R., Ullman, D.H.: Fractional Graph Theory. John Wiley and Son Inc., New York (1997)MATH
22.
Yang, J., Ma, Y., Liu, G.: fractional \((g, f)\)-factor in graphs. Acta Mathematica Scientia 16(4), 385–390 (2001)MATH
Metadata
Title
Optimal Algorithm of Isolated Toughness for Interval Graphs
Authors
Fengwei Li
Qingfang Ye
Hajo Broersma
Xiaoyan Zhang
Copyright Year
2021
Book
Parallel and Distributed Computing, Applications and Technologies

Print ISBN: 978-3-030-69243-8

Electronic ISBN: 978-3-030-69244-5

Copyright Year: 2021

DOI
https://doi.org/10.1007/978-3-030-69244-5_34

Premium Partner

    Image Credits