Paper Info
Title
Hardness results for isomorphism and automorphism of bounded valence graphs
Abstract
In a bounded valence graph every vertex has O(1) neigh- bours. Testing isomorphism of bounded valence graphs is known to be in P (15), something that is not clear to hold for graph isomorphism in general. We show that testing isomorphism for undirected, directed and colored graphs of valence 2 is logspace complete. We also prove the fol- lowing: If a special version of bounded valence GI is hard for ModkL then it is also hard for #L. All results are proved with respect to DLOGTIME uniform AC0 many-one reductions.
Year
Venue
Keywords
2008
SOFSEM (2)
graph isomorphism
Field
DocType
Citations 
Graph canonization,Graph automorphism,Discrete mathematics,Combinatorics,Group isomorphism,Graph isomorphism,Graph homomorphism,Induced subgraph isomorphism problem,Isomorphism,Order isomorphism,Mathematics
Conference
1
PageRank 
References 
Authors
0.37
17
1
Name
Order
Citations
PageRank
Fabian Wagner1203.87