The graph clustering problem has a perfect zero-knowledge interactive proof

Authors
De Santis, A De Crescenzo, G Goldreich, O Persiano, G
Citation
A. De Santis et al., The graph clustering problem has a perfect zero-knowledge interactive proof, INF PROCESS, 69(4), 1999, pp. 201-206
Citations number
17
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
69
Issue
4
Year of publication
1999
Pages
201 - 206
Database
ISI
SICI code
0020-0190(19990226)69:4<201:TGCPHA>2.0.ZU;2-X
Abstract
The input to the Graph Clustering Problem consists of a sequence of integer s m(1),...,m(c) and a sequence of Sigma(i=1)(c) m(i) graphs. The question i s whether the equivalence classes, under the graph isomorphism relation, of the input graphs have sizes which match the input sequence of integers. In this note we show that this problem has a (perfect) zero-knowledge interac tive proof system. (C) 1999 Published by Elsevier Science B.V. All rights r eserved.