Finding the Maximum Number of Node-disjoint Cycles

From: Glenn C. Rhoads (gcrhoads_at_yahoo.com)
Date: 12/12/03 

Date: 11 Dec 2003 18:31:47 -0800

I have an application where I need to find the maximum number
of node-disjoint cycles in an undirected graph. The problem
is NP-complete but the graph is small enough and "nice" enough
that it should be easily doable. I would appreciate it if
someone would point me to a description of a simple algorithm
for solving this problem.

The graph is a *subgraph*, of a two-dimensional mesh unioned
with one special node that is adjacent to every node on the
boundary of the mesh. The size of the mesh could be anywhere
from 5x5 through 10x10. The subgraph will contain all the
nodes but most of the potential edges will be absent. A
typical 10x10 case would contain say 5 nodes of degree 3,
one node of degree 4, a few isolated nodes, the special node
of degree of degree around 8 or 10, and every other node would
have degree 2. For such graphs, it is pretty simple to find
a maximal set of node disjoint cycles by hand, but I need to
repeat this process many times in a computer program.

Relevant Pages

  • Re: how to search mesh topology
    ... The trick is to construct the graph based on ... > 1) Construct a global edge list that contain all unique edges from your ... a way to search the mesh ... ... regions/volumes right now and just find every edge in the entire mesh ...
    (comp.graphics.algorithms)
  • problem with 3d solid
    ... i want to do nice 3d graph, but not using plot3, i would ... my solid is something similiar to cylinder - i have control ... having x,y,z i would like to have a nicer graph that is the ... but neither with mesh or surface something is wrong. ...
    (comp.soft-sys.matlab)
  • Re: How come Ada isnt more popular?
    ... The difference is between a) graph treated as a mesh of nodes which "own" each other and b) graph treated as a collection of nodes. ... The former might have ownership cycles between nodes, but not the latter, where ownership is an acyclic relation between graph and nodes. ... there is a strong argument is that for some class of algorithms it might be beneficial to be able to "drop on the floor" a bigger part of the graph altogether. ...
    (comp.lang.ada)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... I agree that all nodes in the left graph will get the same value, and all nodes in the right graph will get the same value, but those two values will be different. ... Take the arbitrary initial values for the nodes as A for the special node and B for the rest. ... Then the hashes for a 3-node connected subgraph of your right graph are, listing the special node first, ... Hash values will appear in the left graph that are not the right, and that fact should persist through further processing when the other nodes are special and on into the combination of all of a node's hash values into a final hash value for the node. ...
    (sci.crypt)
  • Re: 3D plot being evaluated in two directions
    ... them on a 3d graph with their h values as the z axis. ... problem is that the graph isn't smooth, ... but when i use mesh the lines of the mesh don't go in two ... directions either) on top of each other. ...
    (comp.soft-sys.matlab)