Opened 13 years ago

Closed 13 years ago

#7528 closed enhancement (fixed)

Orientation of a graph with minimized out-degree

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.3
Component: graph theory Keywords:
Cc: Merged in: sage-4.3.rc1
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by ncohen)

The function minimum_outdegree_orientation() returns a DiGraph? which is an orientation of the current graph, such that the maximum out-degree is minimized.

Uses LP !

Nathann

Attachments (1)

trac_7528.patch​ (4.0 KB) - added by ncohen 13 years ago.

Download all attachments as: .zip

Change History (7)

comment:1 Changed 13 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 13 years ago by ncohen

  • Summary changed from Orientation of a graph with bounded out-degree to Orientation of a graph with minimized out-degree

comment:3 Changed 13 years ago by rlm

  • Status changed from needs_review to needs_info

I'm ready to give this a positive review, except there is a conflict: 

Given a complete bipartite graph `K_{n,m}`, the minimum  
outdegree of an orientation is  
`\left\lceil \frac {nm} {n+m}\right\rceil`:: 

sage: g = graphs.CompleteBipartiteGraph(3,4) 
sage: o = g.minimum_outdegree_orientation() # optional - requires GLPK or CBC 
sage: max(o.out_degree()) == ceil((4*3)/(3+4)) # optional - requires GLPK or CBC 
True

Should "the minimum outdegree" be "the smallest possible maximum outdegree", or something similar?

Changed 13 years ago by ncohen

comment:4 Changed 13 years ago by ncohen

  • Status changed from needs_info to needs_review

Indeed ! ( corrected )

comment:5 Changed 13 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to positive_review

comment:6 Changed 13 years ago by mhansen

  • Merged in set to sage-4.3.rc1
  • Milestone changed from sage-4.3.1 to sage-4.3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.