Some complexity theoretic aspects of graph isomorphism and related problems (Record no. 48828)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 02338nam a2200253Ia 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 160627s2010||||xx |||||||||||||| ||und|| |
| 080 ## - UNIVERSAL DECIMAL CLASSIFICATION NUMBER | |
| Universal Decimal Classification number | HBNI Th 19 |
| 100 ## - MAIN ENTRY--AUTHOR NAME | |
| Personal name | Das, Bireswar |
| Relator term | author |
| 245 ## - TITLE STATEMENT | |
| Title | Some complexity theoretic aspects of graph isomorphism and related problems |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Year of publication | 2010 |
| 300 ## - PHYSICAL DESCRIPTION | |
| Number of Pages | 143p. |
| 502 ## - DISSERTATION NOTE | |
| Dissertation note | 2010 |
| 502 ## - DISSERTATION NOTE | |
| Degree Type | Ph.D |
| 502 ## - DISSERTATION NOTE | |
| Name of granting institution | HBNI |
| 520 3# - SUMMARY, ETC. | |
| Summary, etc | The complexity of graph isomorphism problem for restricted classes of graphs are studied and the complexity of group theoretic problems related graph isomorphism are investigated. Several problems closely related to the graph isomorphism problem are classified in Algorithmic graph theory in the classes PZK and SZK. A constant round perfect zero knowledge proof is given for the group isomorphism problem when the groups are given by their multiplication tables. The prover and the verifier in this proof system use only polylogarithmically many random bits. On this motivation, Honest Verifier Statistical Zero Knowledge(HVSZK) proof is studied where the prover, verifier and the simulator use polylogarithmic randomness but also has polylogarithmic message size and only 2 rounds. A polynomial-time oracle algorithm is given for Tournament Canonization that accesses oracles for Tournament Isomorphism and Rigid-Tournament Canonization. Extending the Babai-Luks Tournament Canonization algorithm, an n^O( k^2 + log n) is given for canonization and isomorphism testing of k-hypertournaments, where n is the number of vertices and k is the size of hyper edges. A FPT algorithm is given for the bounded color class hypergraph isomorphism problem which has run-time (b!2^O(b))(N^O(1)), where b is the size of the largest color class and N is the input size. It is proved that the isomorphism and canonization problem for k-tree is in the class StUL which is contained in UL. It is also proved that the isomorphism problem for k-path is complete for L under disjunctive truth-table reductions computable in uniform AC^0. |
| 650 14 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical Term | Computer Science |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Complexity Theory |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Graph Isomorphism |
| 653 10 - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | HBNI Th 19 |
| 720 1# - ADDED ENTRY--UNCONTROLLED NAME | |
| Thesis Advisor | Arvind, V. |
| Relator term | Thesis advisor [ths] |
| 856 ## - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | http://www.imsc.res.in/xmlui/handle/123456789/179 |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Koha item type | THESIS & DISSERTATION |
| Withdrawn status | Lost status | Damaged status | Not for loan | Current library | Full call number | Accession Number | Uniform Resource Identifier | Koha item type |
|---|---|---|---|---|---|---|---|---|
| IMSc Library | HBNI Th 19 | 63454 | http://www.imsc.res.in/xmlui/handle/123456789/179 | THESIS & DISSERTATION |