home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / ai / 4306 < prev    next >
Encoding:
Internet Message Format  |  1992-11-16  |  2.2 KB
  1. Path: sparky!uunet!mcsun!julienas!corton!ilog!lepape
  2. From: lepape@ilog.fr (Claude Le Pape)
  3. Newsgroups: comp.ai
  4. Subject: Re: efficient calculation of path distances in temporal databases.
  5. Keywords: Temporal reasoning, path distance, backtracking
  6. Message-ID: <24941@ilog.fr>
  7. Date: 16 Nov 92 18:31:04 GMT
  8. References: <1992Nov10.144034.2380@fel.tno.nl>
  9. Reply-To: lepape@ilog.UUCP (Claude Le Pape)
  10. Organization: ILOG SA, 2, Avenue Gallieni, BP 85, F-94253 Gentilly Cedex, FRANCE
  11. Lines: 41
  12.  
  13.  
  14. In article <1992Nov10.144034.2380@fel.tno.nl>, huyh7@fel.tno.nl (Huy) writes:
  15.  
  16. > We are searching for an efficient path distance calculation algorithm,
  17. > applicable to temporal databases. The temporal database is virtually a graph
  18. > of timepoints connected by edges. The timepoints mark beginnings and endings
  19. > of events. Each edge is labeled by a pair of integers defining respectively
  20. > the minimum and maximum duration between the connected timepoints. For
  21. > instance, if point A and point B are connected by an edge labeled with
  22. > [3,6], the duration of the edge lies within 3 to 6 time units.
  23.  
  24. If your problem is merely to determine the longest path (sum) of minimum
  25. durations (and/or the shortest path of maximum durations) between two 
  26. points, the best buy is probably Ford's algorithm (1956). You shall find
  27. a description of this algorithm in any standard Operations Research
  28. book. My favorite:
  29.     
  30.     M. Gondran and M. Minoux
  31.     Graphs and Algorithms
  32.     John Wiley and Sons, 1984.    
  33.     
  34. The algorithm runs in O(n . e) where n is the number of nodes and e
  35. the number of edges of the graph. Some other algorithms 
  36. (e.g., matrix-based method implementing transitive closure) may
  37. be worth (in terms of CPU time - not space) if you often modify the
  38. graph and n is very very large (my experience in scheduling is that
  39. even for a few hundreds of nodes, Ford's algorithm remains the most
  40. efficient).
  41.  
  42. Note also that it may be worth representing a maximum duration d between
  43. two events e1 and e2 as a minimum duration (- d) between e2 and e1.
  44.  
  45. Claude Le Pape
  46.  
  47.  
  48.     
  49.         -- 
  50.   Claude LE PAPE         net : lepape@ilog.fr
  51.   ILOG S.A.
  52.   2 Avenue Gallieni - BP 85     tel : (33 1) 46 63 66 66
  53.   94253 Gentilly Cedex FRANCE     fax : (33 1) 46 63 15 82
  54.