Computer Science Homework Solutions
Problem
#72494

Graphs - airport problem

(See attached file for full problem description)

Attached file(s):
Attachments
airports.pdf  View File

Attachment Content Summary (Note: view attachment at the above link before purchasing. Actual attachment content may vary slightly from that shown below.)

airports.pdf
Suppose you are given a timetable, which consists of:

· a set A of N airports, and for each airport a A, a minimum connecting
time c(a);
· a set F of M flights, and for each flight f A, the following information:

­ origin airport a1 (f) A;
­ destination airport a2 (f) A;
­ departure time t1 (f); and
­ arrival time t2 (f).

Give an efficient algorithm for the following problem:

Given airports a and b, and a time t, find a sequence of flights that allows
one to arrive at the earliest possible time in b when departing from a at or
after time t. Minimum connecting times at intermediate airports should
be observed.

Also, give the time complexity of your algorithm as a function of N and M .
Solution
What is this?
By OTA - Overall OTA Rating
Xiao Liu, MS - 4.7/5
Purchase Cost Now
$2.19 CAD (was ~$31.92)
Included in Download
  • Plain text response
  • Attached file(s):
    • airport_algorithm.doc
$2.19 Instant Download
Add to Cart
Why you can trust BrainMass.com
  • Your Information is Secure
  • Best Online Academic Help Service
  • Students find real academic Success
Related Solutions
  • Microsoft Excel S1-P1 - 1. You have received a message from Melissa Gehring of First Choice Travel with quoatations for return airfare, hotel, and airport transfers for the film crew to travel to Toronto for the location sho ...
  • Multiple x and y axes on a single graph - I am trying to graph multiple x and y axes on one graph. I have enclosed a written example. I want my graph on excel to look just like it.
  • Programming Concept - Please describe this program for me. (See attached files for full problem description)
  • SQL Queries - What is the capacity of a particular airplane type? - A small airport: We require a data base for a small airport. The data base should track airplanes, pilots, hangars, airplane types, mechanics and airplane owners. The airport maintains the usual d ...
  • CSCI Excel 2003 - CSCI Excel 2003. See attached file for full problem description.
Browse