Succinct Encodings of Graph Isomorphism

Show simple item record Das, Bireswar
dc.contributor.editor Dediu, A.-H.
dc.contributor.editor Martín-Vide, C.
dc.contributor.editor Sierra-Rodríguez, J.-L.
dc.contributor.editor Truthe, B. 2014-03-19T19:38:40Z 2014-03-19T19:38:40Z 2014
dc.identifier.citation Das, Bireswar; Scharpfenecker, Patrick and Torán, Jacobo,“Succinct Encodings of Graph Isomorphism", in Language and Automata Theory and Applications, DOI: 10.1007/978-3-319-04921-2_23,Cham: Springer International Publishing, 2014, pp. 285-296, ISBN: 978-3-319-04920-5. en_US
dc.identifier.isbn 9783319049205
dc.description.abstract It is well known that problems encoded with circuits or formulas generally gain an exponential complexity blow-up compared to their original complexity. We introduce a new way for encoding graph problems, based on CNF or DNF formulas. We show that contrary to the other existing succinct models, there are examples of problems whose complexity does not increase when encoded in the new form, or increases to an intermediate complexity class less powerful than the exponential blow up. We also study the complexity of the succinct versions of the Graph Isomorphism problem. We show that all the versions are hard for PSPACE. Although the exact complexity of these problems is not known, we show that under most existing succinct models the different versions of the problem are equivalent. We also give an algorithm for the DNF encoded version of GI whose running time depends only on the size of the succinct representation. en_US
dc.description.statementofresponsibility by Bireswar Das
dc.format.extent pp. 285-296
dc.language.iso en en_US
dc.publisher Springer en_US
dc.relation.ispartofseries Lecture Notes in Computer Science;Vol. 8370
dc.subject Complexity en_US
dc.subject Graphisomorphism en_US
dc.subject Succinct en_US
dc.subject.ddc 006.31
dc.title Succinct Encodings of Graph Isomorphism en_US
dc.type Book chapter en_US

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


My Account