THE HOMOGENEOUS SET SANDWICH PROBLEM

Authors
CERIOLI MR EVERETT H DEFIGUEIREDO CMH KLEIN S
Citation
Mr. Cerioli et al., THE HOMOGENEOUS SET SANDWICH PROBLEM, Information processing letters, 67(1), 1998, pp. 31-35
Citations number
14
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
67
Issue
1
Year of publication
1998
Pages
31 - 35
Database
ISI
SICI code
0020-0190(1998)67:1<31:THSSP>2.0.ZU;2-J
Abstract
The graph sandwich problem for property Phi is defined as follows: Giv en two graphs G(1) = (V, E-1) and G(2) = (V, E-2) such that E-1 subset of or equal to E-2, is there a graph G = (V, E) such that E-1 subset of or equal to E subset of or equal to E-2 which satisfies property Ph i? We present a polynomial-time algorithm for solving the graph sandwi ch problem, when property Phi is ''to contain a homogeneous set''. The algorithm presented also provides the graph G and a homogeneous set i n G in case it exists. (C) 1998 Elsevier Science B.V. All rights reser ved.