Project Detail

Discrete mathematics wizard – graph theory   Featured

Discrete mathematics wizard – graph theory is project number 340107
posted at GetAFreelancer.com. Click here to post your own project.

 

Bookmark and Share
Free Trial For New Buyers
 

Status: Closed
(Selected Service Provider)

Selected Providers: DrRR

Budget: $250-600

Created: 11/07/2008 at 9:35 EST

Bid Count: 13

Average Bid: $ 580

11/09/2008 at 9:35 EST

Project Creator: richtj View PM Post PM
Employer Rating: (No Feedback Yet)

Bid On This Project
 

Description

Warning: Three people have failed so far to come up with a solution and lots of time was wasted. The mathematics behind this project is difficult!

Please bid only if you have a very good understanding of graph theory and now how to program the functions. Only providers with good references will be considered. You must be able to start work immediately.

Your task will be to assist the development of an visualization tool with a custom mathematical algorithm. The tool enables the user to view complex project relationships drawn in 2D.

You will have to develop a mathematical algorithm to figure out the best possible placement (X and Y) coordinates of the projects to minimize the number of lines (representing relationshis) crossing each other as well as the overall length of all lines combined. The primary goal of the algorithm is to draw a picture that is easy for the user to follow and understand. Please take a look at the attached graphic.

The algorithm should work for any number projects. The goal is reached when the dynamically generated picture cannot be improved manually. The code will be need to be scripted in VB and incorporated in Excel. An additional programmer will be available to assist. The excel will output an XML file which will be used by a separate program to generate the graphic.

From a mathematical standpoint the problem is similar to the automatic routing feature for the design of circuits / chip design.

Please take a look at the attached jpg.

Please message me if you have questions.



Additional files submitted:
project_example.jpg

Messages Posted: 3 View project clarification board Post message on project clarification board

Bid On This Project
 
If you are the project creator or one of the bidders Log In for more options

  View PM Post PM

600

10 days

11-07-2008 12:55 EST

Hi, Please see your PM. Best Regards, Yousef

help

  View PM Post PM

600

20 days

11-07-2008 09:42 EST

Ready to do please check reference work.

help

  View PM Post PM

600

10 days

11-07-2008 14:18 EST

Hello - Please see PMB for details of my bid. - Thank you.

help

  View PM Post PM

600

15 days

11-07-2008 18:51 EST

I would try an iterative positionning by simulating physical forces. imagine each link is a wire or a string. the longer the link is, the higher would be the strength. this constraint is not enough of course, there should be an opposite repulsive force to avoid every nodes to collapse in the center. to guarantee a minimal spacing, I would apply the equivalent of an electrical charge to each node to make them push each over. During thousands of cycles, positions would arrange themselves. when it stops moving, the optimal has been found. for example, if 3 projects are linked to a fourth one. they will arrange themselves to form 120 degrees sectors because that would give an equal distance, so equal forces... When I was a beginner, I did that in 3D to find an optimal geodesical volume. Of course, if you have more than 100 nodes, computing time increases a lot. I had also to deal with foatting point truncation errors. And I made a few exceptions to the free moving rule : one node must be fixed to avoid the hole figure to shift because of truncation errors. Another node (the farest one) must be bound to a line crossing the center to avoid the hole thing to rotate for the same reasons.

help

  View PM Post PM

550

21 days

11-07-2008 12:04 EST

Wecan provide you with exactly what you are looking for. Best Regards Mike

help

  View PM Post PM

600

18 days

11-07-2008 12:18 EST

(No Feedback Yet)

I can do it. Math is my major. Have a similar program for graph visualization

help

  View PM Post PM

600

15 days

11-07-2008 12:35 EST

(No Feedback Yet)

BizSol is providing e-commerce, e-marketing, e-business, MobileCommerce, VoIP, P2P, Mobile Games, Mobile Software Development and ERP solutions. We focus on empowering your business by introducing a business-driven approach to development. It is our commitment to provide real time, cutting edge business solutions, and have long-term business relations by delighting all those who are touched by our services. Our dedicated professionals are always ready to serve our valuable clients. Regards BizSol Team

help

  View PM Post PM

500

28 days

11-07-2008 13:37 EST

(No Feedback Yet)

i would deliver within the stipulated time

help

  View PM Post PM

590

21 days

11-07-2008 17:56 EST

(No Feedback Yet)

I'll do it.

help

  View PM Post PM

600

21 days

11-09-2008 00:20 EST

(No Feedback Yet)

Hi: You CANNOT simultaneously minimize the number of lines crossing each other as well as the overall length of all lines combined. As I pointed out in your previous post of the same problem, the problem is very close to the minimum crossing number problem in graph theory. You need someone who understands discrete math and algorithm formulation specifically for the class called NP Complete combinatorial optimization problems, to advise you on problem formulation and to design your algorithm. If the algorithm is designed correctly, coding it is child's play. I would be happy to help you with this project. I would be able to contribute in terms of building the algorithm and reviewing the algorithm implementation code (I am a capable programmer too). My bid is for providing the algorithm and reviewing the implementation code in detail. I have a PhD in Combinatorial Optimization and a published paper in the journal "Mathematical Programming" which is considered the #1 journal in discrete math; that should be sufficient to prove my credentials in discrete math. Thank you! -Ram

help

  View PM Post PM

600

20 days

11-08-2008 20:06 EST

(No Feedback Yet)

Hey, if you can't find someone that can help you on this, I would be willing to take a crack at it. I don't have a degree but I have independently read stephen hawking, einstein, and looked over their formulas. I have a very outside view of things and perhaps could have a fresh perspective to troubleshoot. If I can tell immediately that it is out of my league, I'd let you know as soon as I review the project. I won't lead you on.

help

  View PM Post PM

600

20 days

11-09-2008 08:55 EST

(No Feedback Yet)

I could help to you, I did some simulators (about graph teory, NP Complete and routes). I know about VBScript and XML. The last simultator I did, was one to optimize paths, It was done in VB. Regards. Josue Rojas

help

  View PM Post PM

500

15 days

11-09-2008 09:42 EST

(No Feedback Yet)

Hi! I can do this project for you! i have large experience in this domain! For details and samples of my work please contact me by PM and we'll discuss time and best ways to perform your project! Have a nice day.

help

    Bid on this Project