Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)

by

As you pointed out, the problem is equivalent to the problem of finding a maximum matching in a bipartite graph (one set of vertices is the set of people and the other on the set of slots, there is an edge between a person and a slot if the person is available for this slot).

This problem can be solved with the Hopcroft-Karp algorithm.

Complexity O(n^(5/2)) in the worst case, better if the graph is sparse.

More Related Contents:

  1. Cycles in an Undirected Graph
  2. Millions of 3D points: How to find the 10 of them closest to a given point?
  3. Graph auto-layout algorithm
  4. Find connected components in a graph [closed]
  5. Finding all the shortest paths between two nodes in unweighted undirected graph
  6. Algorithm for “nice” grid line intervals on a graph
  7. How to implement depth first search for graph with a non-recursive approach
  8. Longest acyclic path in a directed unweighted graph
  9. help in the Donalds B. Johnson’s algorithm, i cannot understand the pseudo code (PART II)
  10. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  11. What algorithm to use to determine minimum number of actions required to get the system to “Zero” state?
  12. Enumerating all paths in a directed acyclic graph
  13. How does Dijkstra’s Algorithm and A-Star compare?
  14. Find cycle of shortest length in a directed graph with positive weights
  15. graph – Dijkstra for The Single-Source Longest Path
  16. Planar Graph Layouts
  17. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  18. Bridges in a connected graph
  19. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  20. Finding connected components of adjacency matrix graph
  21. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1
  22. Complexity of absolute difference and sum
  23. How to compute Discrete Fourier Transform?
  24. Difference between Big-O and Little-O Notation
  25. search for interval overlap in list of intervals?
  26. robust algorithm for surface reconstruction from 3D point cloud?
  27. Is there ever a good reason to use Insertion Sort?
  28. Coin changing algorithm
  29. Search a sorted 2D matrix [duplicate]
  30. What are the pitfalls in implementing binary search? [closed]

Leave a Comment