ダウンロード数: 186
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
978-3-540-72870-2_17.pdf | 345.52 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Kamiyama, Naoyuki | en |
dc.contributor.author | Katoh, Naoki | en |
dc.contributor.author | Takizawa, Atsushi | en |
dc.date.accessioned | 2009-08-21T04:38:42Z | - |
dc.date.available | 2009-08-21T04:38:42Z | - |
dc.date.issued | 2008 | - |
dc.identifier.isbn | 9783540728689 | - |
dc.identifier.uri | http://hdl.handle.net/2433/84858 | - |
dc.description | Algorithmic aspects in information and management : Third International Conference, AAIM 2007, Portland, OR, USA, June 6-8, 2007 : proceedings : (Lecture notes in computer science ; 4508) | en |
dc.description | Proc. of 3rd Int. Conf. on Algorithmic Aspect in Information and Management. (AAIM 2007) | en |
dc.description.abstract | In this paper, we consider the evacuation problem for a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [1] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a dynamic network with a single sink s such that (i) for each vertex v the sum of transit times of arcs on any path from v to s takes the same value, and (ii) for each vertex v the minimum v-s cut is determined by the arcs incident to s whose tails are reachable from v. We propose an efficient algorithm for this network problem. This class of networks is a generalization of the grid network studied in the paper [2]. | en |
dc.language.iso | eng | - |
dc.publisher | Springer | en |
dc.rights | The original publication is available at www.springerlink.com. | en |
dc.rights | This is not the published version. Please cite only the published version. | en |
dc.rights | この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 | ja |
dc.title | An Efficient Algorithm for the Evacuation Problem in a Certain Class of a Network with Uniform Path-Lengths (Algorithmic Aspects in Information and Management) | en |
dc.type | conference paper | - |
dc.type.niitype | Conference Paper | - |
dc.identifier.jtitle | Lecture notes in computer science | en |
dc.identifier.volume | 4508 | - |
dc.identifier.spage | 178 | - |
dc.identifier.epage | 190 | - |
dc.relation.doi | 10.1007/978-3-540-72870-2_17 | - |
dc.textversion | author | - |
dcterms.accessRights | open access | - |
dc.relation.isIdenticalTo | BA82342418 | - |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。