RECOGNIZING STRICT 2-THRESHOLD GRAPHS IN O(M) TIME

Authors
PETRESCHIM R STERBINI A
Citation
R. Petreschim et A. Sterbini, RECOGNIZING STRICT 2-THRESHOLD GRAPHS IN O(M) TIME, Information processing letters, 54(4), 1995, pp. 193-198
Citations number
9
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
54
Issue
4
Year of publication
1995
Pages
193 - 198
Database
ISI
SICI code
0020-0190(1995)54:4<193:RS2GIO>2.0.ZU;2-B
Abstract
In this paper we show an O(m) time recognition algorithm for a class o f graphs named Strict 2-Threshold that have threshold number 2. Our al gorithm improves the previously known O(m(2)) algorithm and generates the two threshold components. The algorithm can be easily adapted to r ecognize 2-threshold graphs with exactly three cutpoints.