Resource Constrained Shortest Paths

Mehlhorn, Kurt; Ziegelmann, Mark

doi:10.1007/3-540-45253-2_30

Resource Constrained Shortest Paths

Mehlhorn, K., & Ziegelmann, M. (2000). Resource Constrained Shortest Paths. In M., Paterson (Ed.), Algorithms - ESA 2000 (pp. 326-337). Berlin, Germany: Springer.

Item is 公開

表示: 全項目非表示: 全項目

基本情報

表示: 非表示:

アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-3349-9 版のパーマリンク: https://hdl.handle.net/21.11116/0000-000E-455E-C

資料種別: 会議論文

ファイル

表示: ファイル

非表示: ファイル

:

153.pdf (出版社版), 108KB

ファイルのパーマリンク:
-

ファイル名:
153.pdf

説明:
-

OA-Status:

閲覧制限:
非公開

MIMEタイプ / チェックサム:
application/pdf

技術的なメタデータ:

著作権日付:
-

著作権情報:
-

CCライセンス:
-

:

Mehlhorn153.pdf (出版社版), 121KB

ファイルのパーマリンク:
-

ファイル名:
Mehlhorn153.pdf

説明:
-

OA-Status:

閲覧制限:
非公開

MIMEタイプ / チェックサム:
application/pdf

技術的なメタデータ:

著作権日付:
-

著作権情報:
-

CCライセンス:
-

作成者

表示:

非表示:

作成者:
Mehlhorn, Kurt¹, 著者
Ziegelmann, Mark¹, 著者

所属:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

内容説明

表示:

非表示:

キーワード: -

要旨: The resource constrained shortest path problem (CSP) asks for the computation
of a least cost path obeying a set of resource constraints. The problem is
NP-complete. We give theoretical and experimental results for CSP. In the
theoretical part we present the hull approach, a combinatorial algorithm
for solving a linear
programming relaxation and prove that it runs in polynomial time in the case of
one resource. In the experimental part we compare the hull approach to previous
methods for solving the LP relaxation and give an exact algorithm based on
the hull approach. We also compare our exact algorithm to previous
exact algorithms and approximation algorithms for the problem.

資料詳細

表示:

非表示:

言語: eng - English

日付: 修正: 2008-01-04出版: 2000

出版の状態: 出版

ページ: -

出版情報: -

目次: -

査読: -

識別子（DOI, ISBNなど）: eDoc: 344447
その他: Local-ID: C1256428004B93B8-7B769F17BCB8113EC12569D6003664F6-MehlhornZiegelmann2000
DOI: 10.1007/3-540-45253-2_30
BibTex参照ID: Mehlhorn-Ziegelmann_ESA2000

学位: -

訴訟

表示:

Project information

表示:

出版物 1

表示:

非表示:

出版物名: Algorithms - ESA 2000

副タイトル : 8th Annual European Symposium

省略形 : ESA 2000

種別: 会議論文集

著者・編者:
Paterson, Mike¹, 編集者

所属:
1 External Organizations, ou_persistent22

出版社, 出版地: Berlin, Germany : Springer

ページ: - 巻号: - 通巻号: - 開始・終了ページ: 326 - 337 識別子（ISBN, ISSN, DOIなど）: ISBN: 978-3-540-41004-1

出版物 2

表示:

非表示:

出版物名: Lecture Notes in Computer Science

省略形 : LNCS

種別: 連載記事

著者・編者:

所属:

出版社, 出版地: -

ページ: - 巻号: 1879 通巻号: - 開始・終了ページ: - 識別子（ISBN, ISSN, DOIなど）: -

アイテム詳細

基本情報

ファイル

関連URL

作成者

内容説明

資料詳細

関連イベント

訴訟

Project information

出版物 1

出版物 2