CODEWITHSUNDEEP
algorithmgraph-theory
Qwertuy
Qwertuy

Reputation: 198

Algorithm to find maximal independent set on a hexagonal/benzenoid graph

Given a graph G=(V,E), I want to find all maximal sets of independent edges. In general, this can be achieved by brute-force methods that have exponential complexity. However, I am concerned only with bipartite benzenoid graphs; i.e, those formed by the carbon atoms of poly aromatic hydrocarbons. The problem of finding these maximal sets is equivalent to that of finding the maximal number of Clar's sextets (aromatic rings) in the structure, hence the interest of this application in chemistry. Are there more efficient algorithms to find the maximal set of independent edges in such a case?

Upvotes: 0

Views: 92

Answers (1)

ravenspoint
ravenspoint

Reputation: 20596

Assuming you have set up an adjacency list that makes finding node at other end of edge from a node easy and fast:

LOOP A over nodes
    IF A is carbon
        IF A has two or more bonds to another carbon
             IF A has one double bond to another carbon
                 Add A to list of potential ring members
LOOP A over list of potential ring members
    SET A2 to node at other end of double bond from A AND in list of potential ring members
    SET A3 to node at other end of single bond from A2 AND in list of potential ring members
    SET A4 to node at other end of double bond from A3 AND in list of potential ring members
    SET A5 to node at other end of single bond from A4 AND in  list of potential ring members    
    SET A6 to node at other end of double bond from A5 AND in list of potential ring members
    IF A6 == A
        add A...A6 to list of rings
        remove A...A6 from list of potential ring members

Note if any of the SETs are not possible, CONTINUE to next iteration of loop.

Upvotes: 1

Related Questions