Editorial/Data Protection
Applications for the Methods of graph solutions

Shortest Paths

  • Tour with shortest distance or travel time
  • Tour with lowest cost
  • Fastest workflow: process a task in minimum total time for succesive activities (network planning)

Minimum Spanning Tree

  • Routes for public mains supply (gas, water, electric power, phone, data)

Traveling Salesman Problem (TSP)

  • Order of visiting a saleman`s customers
  • Order of roll out of a parcel service`s packets
  • Order of dropping passengers of a hailed shared taxi
  • Order of drilling holes

Chinese Postman Problem

  • Order in which a postman passes streets of houses
  • Order in which garbage collection collects garbage cans

Maximum Flow

  • Capacity of public mains supply (gas, water, electric power, phone, data)

Minimum Cost Flow

  • Transportation routes to cover the demand of several customers by several supplies at minimum cost (Transportation Problem)
  • Transportation routes for the provision of customers by several supplies using transshipment stations at minimum cost (Transshipment Problem)
  • Transportation route with minimum cost using routes with constrained capacities
  • Transportation route with shortest distance or travel time using routes with constrained capacities

Bipartite Matching

  • Assignment of activities/demands to workers/supplies at minimum total cost

General Matching

  • Pairwise combinations that yield minimum cost
Editorial/Data Protection • page checked on Oct. 4th 2005