a mathematical structure that contains a collection of vertices or 'nodes' and a collection of edges that connect pairs of vertices

learn more… | top users | synonyms

5
votes
2answers
1k views

Algorithm for an exact solution to the Travelling Purchaser Problem

do you know of any algorithms which give an exact solution for the Traveling Purchaser Problem. I can only find heuristic and probabilistic approaches. I do have implemented a genetic algorithm so ...
5
votes
3answers
2k views

What is an algorithm to find simple cycles?

I have a graph with an Eulerian cycle and no Hamiltonian cycles. I would like to divide this graph into simple cycles. Edges may not be repeated in simple cycles. How can this be done?
18
votes
6answers
723 views

Visiting points on a number line while minimizing a cost not related to distance

I need some help on this ACM ICPC problem. My current idea is to model this as a shortest path problem, which is described under the problem statement. Problem There are N = 1000 nuclear waste ...
10
votes
2answers
743 views

How to represent a graph with multiple edges allowed between nodes and edges that can selectively disappear

I'm trying to figure out what sort of data structure to use for modeling some hypothetical, idealized network usage. In my scenario, a number of users who are hostile to each other are all trying to ...
4
votes
4answers
446 views

Building a route creator

Ok, already up front, I'm going to tell you, that this is a bonus task for Data structure course I'm taking. That should take care of all the questions whether or not this is for a homework. Route ...
3
votes
2answers
197 views

Custom graph comparison?

I'm trying to compare two graphs using hash value ( i.e, at the time of comparison, try to avoid traversing the graph ) Is there a way to make a function such that the hash values compared can also ...
1
vote
1answer
211 views

Why does this algorithm work in O(n m)?

This is from a blog post on Codeforces. I couldn't really understand why the editorialist goes on to claim that this code works in O(n m) This is a graph problem, where we are supposed to find the ...