期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1998
卷号：1998
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The input to the {\em Graph Clustering Problem}\/
consists of a sequence of integers m1mt
and a sequence of ti=1mi graphs.
The question is 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
interactive proof system.
This result improves over ECCC TR96-054,
where a parametrized (by the sequence of integers)
version of the problem was studied.
