Computing the Weighted Isolated Scattering Number of Interval Graphs in Polynomial Time

Complexity 2019:1-8 (2019)
  Copy   BIBTEX

Abstract

The scattering number and isolated scattering number of a graph have been introduced in relation to Hamiltonian properties and network vulnerability, and the isolated scattering number plays an important role in characterizing graphs with a fractional 1-factor. Here we investigate the computational complexity of one variant, namely, the weighted isolated scattering number. We give a polynomial time algorithm to compute this parameter of interval graphs, an important subclass of perfect graphs.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,616

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.
Cancellation laws for polynomial-time p-isolated sets.John N. Crossley & J. B. Remmel - 1992 - Annals of Pure and Applied Logic 56 (1-3):147-172.
Light affine lambda calculus and polynomial time strong normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
Feasible graphs with standard universe.Douglas Cenzer & Jeffrey B. Remmel - 1998 - Annals of Pure and Applied Logic 94 (1-3):21-35.
On the Complexity of Alpha Conversion.Rick Statman - 2007 - Journal of Symbolic Logic 72 (4):1197 - 1203.
Le Probleme des Grandes Puissances et Celui des Grandes Racines.Natacha Portier - 2000 - Journal of Symbolic Logic 65 (4):1675-1685.
A Note on The Functions Which Are Not Polynomial Time Computable From Their Graphs.Asae Mochizuki & Juichi Shinoda - 1996 - Annals of the Japan Association for Philosophy of Science 9 (1):17-21.

Analytics

Added to PP
2019-03-12

Downloads
7 (#1,201,537)

6 months
1 (#1,042,085)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references