Name
Abstract | ||
|---|---|---|
The airlines in the real world form small-world network. This implies that they are constructed with an ad hoc strategy. The
small-world network is not so bad from the viewpoints of customers and managers. The customers can fly to any destination
through a few airline hubs, and the number of airlines is not so many comparing to the number of airports. However, clearly,
it is not the best solution in either viewpoint since there is a trade off. In this paper, one of the extreme cases, which
is the standpoint of the manager, is considered; we assume that customers are silent and they never complain even if they
are required to transit many times. This assumption is appropriate for some transportation service and packet communication.
Under this assumption, the airline problem is to construct the least cost connected network for given distribution of the
populations of cities with no a priori connection. First, we show an efficient algorithm that produces a good network which
is minimized the number of vacant seats. The resultant network contains at most n connections (or edges), where n is the number of cities. Next we aim to minimize not only the number of vacant seats, but also the number of airline connections.
The connected network with the least number of edges is a tree which has exactly n − 1 connections. However, the problem to construct a tree airline network with the minimum number of vacant seats is
NP{\cal NP}
-complete. We also propose efficient approximation algorithms to construct a tree airline network with the minimum number
of vacant seats.
|
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-72504-6_39 | Lecture Notes in Computer Science |
Keywords | DocType | Volume |
small-world network,airline connection,vacant seat,tree airline network,connected network,resultant network,minimum number,airline problem,efficient algorithm,good network,airline hub,small world network,np completeness,spanning tree,approximation algorithm,network design | Conference | 4484 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
4 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shin-ichi Nakano | 1 | 246 | 24.40 |
| Ryuhei Uehara | 2 | 528 | 75.38 |
| Takeaki Uno | 3 | 1319 | 107.99 |