AN O(N(3)) RECOGNITION ALGORITHM FOR BITHRESHOLD GRAPHS

Authors
DEAGOSTINO S PETRESCHI H STERBINI A
Citation
S. Deagostino et al., AN O(N(3)) RECOGNITION ALGORITHM FOR BITHRESHOLD GRAPHS, Algorithmica, 17(4), 1997, pp. 416-425
Citations number
15
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
17
Issue
4
Year of publication
1997
Pages
416 - 425
Database
ISI
SICI code
0178-4617(1997)17:4<416:AORAFB>2.0.ZU;2-R
Abstract
A bithreshold graph is the edge intersection of two threshold graphs s uch that every independent set is independent in at least one of the t hreshold components. Recognizing a bithreshold graph is polynomially e quivalent to recognizing its complement, i.e., a cobithreshold graph. In this paper we introduce a coloring of the vertices and oi the edges of a cobithreshold graph that leads to a recognition and decompositio n algorithm. This algorithm works in O(n(3)) time improving the previo usly known a(n(4)) result [HM].