Jump to content

Recommended Posts

Posted

Recently, a friend of mine asked me to help with the following optimization problem in graph theory:

Given a connected graph, decompose it into 3-vertex groups such that the number of resulting groups is minimal. 3-vertex group must be connected in the original graph: it will have 2 or 3 edges. Obviously, there might be some remainder groups with less than 3 vertices. The goal is to minimize the number of such remainder groups as well.

 

Example: take a map of us. Make states nodes and the borders edges. Take Illinois, Wisconsin, Minnesota, Kentucky, Indiana, Missouri. The solution would produce 2 groups.

 

We have an algorithm that seems to work. However, I'd like to proove that it works for n nodes. Hence, the question to identify the problem in computer science.

 

Thank you!

Dmitriy

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.