Jump to content
  • Advertisement
Sign in to follow this  
Sneftel

Equal end-partitioning of acyclic graph

This topic is 3901 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Alright, so I'm all thinked out, and all googled out, and still haven't gotten anywhere. Here's the deal. Consider an undirected, acyclic graph G = {V,E}. Of the vertices V, there is a set V' ⊂ V of "marked" vertices. (as a potential simplifying assumption, the problem can be reworked such that all elements of V' have degree 1.) The problem: to find an edge e ∈ E such that there are as equal as possible a number of marked vertices on each side of the edge; that is, if e were deleted from the graph, the two resultant components would have as close to the same number of marked vertices as possible. I just know there has to be a graph traversal/dynamic programming solution, but for the life of me I cannot think of one which is more efficient than the brute force approach of iterating through all edges and counting the marked vertices on either side.

Share this post


Link to post
Share on other sites
Advertisement
Wow, I cannot believe I did not see that before. Alright, simple traversal-based solution. Probably not useful or interesting to anybody other than myself, but let me know if you need it.

Share this post


Link to post
Share on other sites
Yeah, it seems to me like you could just pick a random vertex and recurse down to the leafs, counting "special" vertices as you go and storing that information at each vertex/edge. Then you'd have enough information to pick the best edge on the unroll.

Share this post


Link to post
Share on other sites
I wouldn't bother for this particular problem. If you're not familiar with the graph theory terms I've used, though, I'd say you should most certainly spend time getting to know them. They are crucial to being a useful programmer.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!