An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity

Naoyuki Kamiyama; Naoki Katoh; Atsushi Takizawa

doi:10.1093/ietisy/e89-d.8.2372

An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity

Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa

Research output: Contribution to journal › Article › peer-review

29 Citations (Scopus)

Abstract

In this paper, we consider the quickest flow problem in a network which consists of a directed graph with capacities and transit times on its arcs. We present an O(n log n) time algorithm for the quickest flow problem in a network of grid structure with uniform arc capacity which has a single sink where n is the number of vertices in the network.

Original language	English
Pages (from-to)	2372-2379
Number of pages	8
Journal	IEICE Transactions on Information and Systems
Volume	E89-D
Issue number	8
DOIs	https://doi.org/10.1093/ietisy/e89-d.8.2372
Publication status	Published - Aug 2006
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Hardware and Architecture
Computer Vision and Pattern Recognition
Electrical and Electronic Engineering
Artificial Intelligence

Access to Document

10.1093/ietisy/e89-d.8.2372

Cite this

@article{43cdb971eca64bb8960ead114366cc10,

title = "An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity",

abstract = "In this paper, we consider the quickest flow problem in a network which consists of a directed graph with capacities and transit times on its arcs. We present an O(n log n) time algorithm for the quickest flow problem in a network of grid structure with uniform arc capacity which has a single sink where n is the number of vertices in the network.",

author = "Naoyuki Kamiyama and Naoki Katoh and Atsushi Takizawa",

year = "2006",

month = aug,

doi = "10.1093/ietisy/e89-d.8.2372",

language = "English",

volume = "E89-D",

pages = "2372--2379",

journal = "IEICE Transactions on Information and Systems",

issn = "0916-8532",

publisher = "一般社団法人電子情報通信学会",

number = "8",

}

TY - JOUR

T1 - An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity

AU - Kamiyama, Naoyuki

AU - Katoh, Naoki

AU - Takizawa, Atsushi

PY - 2006/8

Y1 - 2006/8

N2 - In this paper, we consider the quickest flow problem in a network which consists of a directed graph with capacities and transit times on its arcs. We present an O(n log n) time algorithm for the quickest flow problem in a network of grid structure with uniform arc capacity which has a single sink where n is the number of vertices in the network.

AB - In this paper, we consider the quickest flow problem in a network which consists of a directed graph with capacities and transit times on its arcs. We present an O(n log n) time algorithm for the quickest flow problem in a network of grid structure with uniform arc capacity which has a single sink where n is the number of vertices in the network.

UR - http://www.scopus.com/inward/record.url?scp=33747836759&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33747836759&partnerID=8YFLogxK

U2 - 10.1093/ietisy/e89-d.8.2372

DO - 10.1093/ietisy/e89-d.8.2372

M3 - Article

AN - SCOPUS:33747836759

SN - 0916-8532

VL - E89-D

SP - 2372

EP - 2379

JO - IEICE Transactions on Information and Systems

JF - IEICE Transactions on Information and Systems

IS - 8

ER -

An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this