Graph isomorphism and volumes of convex bodies

Details Graph isomorphism and volumes of convex bodies Graph isomorphism and volumes of convex bodies

2009-11-09

arxiv.org/abs/0911.1739v1

Computer Science

Computational Complexity

9 pages

Scientific paper

We show that a nontrivial graph isomorphism problem of two undirected graphs, and more generally, the permutation similarity of two given $n\times n$ matrices, is equivalent to equalities of volumes of the induced three convex bounded polytopes intersected with a given sequence of balls, centered at the origin with radii $t_i\in (0,\sqrt{n-1})$, where $\{t_i\}$ is an increasing sequence converging to $\sqrt{n-1}$. These polytopes are characterized by $n^2$ inequalities in at most $n^2$ variables. The existence of fpras for computing volumes of convex bodies gives rise to a semi-frpas of order $O^*(n^{14})$ at most to find if given two undirected graphs are isomorphic.

Affiliated with

Also associated with

No associations

Rating

Graph isomorphism and volumes of convex bodies does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph isomorphism and volumes of convex bodies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph isomorphism and volumes of convex bodies will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-660621