ON THE RECOGNITION OF FAMILIES OF GRAPHS WITH LOCAL COMPUTATIONS

Authors
LITOVSKY I METIVIER Y ZIELONKA W
Citation
I. Litovsky et al., ON THE RECOGNITION OF FAMILIES OF GRAPHS WITH LOCAL COMPUTATIONS, Information and computation, 118(1), 1995, pp. 110-119
Citations number
19
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
118
Issue
1
Year of publication
1995
Pages
110 - 119
Database
ISI
SICI code
0890-5401(1995)118:1<110:OTROFO>2.0.ZU;2-O
Abstract
This paper is a contribution to understanding the power and the limita tions of local computations in graphs. We use local computations to de fine a notion of graph recognition; our model allows a simulation of a utomata on words and on trees. We introduce the notion of k-covering t o examine limitations of such systems. For example, we prove that the family of series-parallel graphs and the family of planar graphs canno t be recognized by means of local computations. (C) 1995 Academic Pres s. Inc.