Maximum weighted sub graph

9 views
Skip to first unread message

soumya hegde

unread,
Jul 14, 2013, 8:29:37 AM7/14/13
to sage-s...@googlegroups.com, soumya hegde
Please let me know how can i form the objective function for finding the maximum weighted sub graph. Constraint will be highest degree of each node can be 2.
I have the below code:

But this code will only give me maximum number of edges that can be included in tha subgraph for the given constarint:

Please correct the code and help me proceed further:


ED=MixedIntegerLinearProgram(maximization=True)
var=ED.new_variable(binary=True)
ED.set_objective(sum([var[Set(e)] for e in DG.edges(labels = True)]))

for v in DG:
edges = DG.edges_incident(v, labels = True)
ED.add_constraint( sum([var[Set(e)] for e in edges]) <= 2 )
ED.solve()
var = ED.get_values(var)
print [e for e,i in var.items() if i]

Reply all
Reply to author
Forward
0 new messages