Tell me more ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
up vote 1 down vote favorite

I have a dense unlabeled graph ( each vertex has got at least 4 incident edges ).

Number of vertices (V) of the graph is always a perfect square.

I want to find all the meshes of $\sqrt{v} {x} \sqrt{v}$ in it.

Are there any known algorithms to accomplish this?

Any help is appreciated.

Thanks!

share|improve this question

1 Answer

up vote 2 down vote accepted

There could easily be an exponential number of meshes (e.g. let your graph be complete). And it's NP-complete to find even one of them (a graph G has a Hamiltonian path if and only the Cartesian product of G with a path contains a mesh).

So, yes, there are algorithms — you can just do a brute force search over all permutations of the vertices, for instance — but not polynomial algorithms.

share|improve this answer
Oh no! I have 256 nodes i.e. 256! possibilities. Yet another attempt to make a million dollars failed. Thanks! :D – Pratik Deoghare Jul 14 '10 at 21:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.