Algorithms for the Homogeneous Set Sandwich Problem |
| |
Authors: | Celina MH de Figueiredo Guilherme D da Fonseca Vinicius GP de Sa Jeremy Spinrad |
| |
Affiliation: | (1) Instituto de Matematica and COPPE, Universidade Federal do Rio de Janeiro, Caixa Postal 68530, 21945-970 Rio de Janeiro, RJ, Brazil;(2) Department of Computer Science, University of Maryland, College Park, MD 20742, USA;(3) School of Engineering, Vanderbilt University, 2201 West End Avenue, Nashville, TN 37235, USA |
| |
Abstract: | A homogeneous set is a non-trivial module of a graph, i.e. a non-empty,
non-unitary, proper subset of a graph's vertices such that all its elements
present exactly the same outer neighborhood. Given two graphs
the Homogeneous Set Sandwich Problem (HSSP) asks whether there
exists a sandwich graph
which
has a homogeneous set. In 2001 Tang et al. published
an all-fast
algorithm which was recently proven wrong, so that the HSSP's known upper bound would have been reset
thereafter at the former
determined by Cerioli et al. in 1998. We present, notwithstanding, new deterministic
algorithms which have it established at
We give as
well two even faster
randomized algorithms, whose simplicity might
lend them didactic usefulness. We believe that, besides providing efficient
easy-to-implement procedures to solve it, the study of these new approaches
allows a fairly thorough understanding of the problem. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|