| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 2022-10-26 11:45 Evacuation problems on grid networks with uniform transit time and uniform capacity Yuki Tokuni, Naoki Katoh, Junichi Teruyama, Yuya Higashikawa (Uoh)  COMP2022-15 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | We consider the problem of finding the minimum time at which all supplies on a dynamic flow network can reach the demand point, which we term Quickest Evacuation Time. Polynomial-time algorithms are known for general networks, but they use the submodular function minimization algorithm as a subroutine, and their computational complexity is a high-order polynomial. In this paper, we propose an efficient polynomial time algorithm for bidirected grid networks with uniform edge capacity and uniform transit time, which does not use a submodular function minimization algorithm. | |
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | dynamic flow network / quickest transshipment problem / polynomial time algorithm / / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 122, no. 229, COMP2022-15, pp. 7-13, Oct. 2022. | |
| Paper # | COMP2022-15 | |
| Date of Issue | 2022-10-19 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | COMP2022-15 |
|
| Conference Information | |
| Committee | COMP |
| Conference Date | 2022-10-26 - 2022-10-26 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Kyusyu Univ. Nishijin Plaza |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Theoretical Computer Science, etc |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2022-10-COMP |
| Language | Japanese |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Evacuation problems on grid networks with uniform transit time and uniform capacity |
| Sub Title (in English) | |
| Keyword(1) | dynamic flow network |
| Keyword(2) | quickest transshipment problem |
| Keyword(3) | polynomial time algorithm |
| Keyword(4) | |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Yuki Tokuni |
| 1st Author's Affiliation | University of Hyogo (Uoh) |
| 2nd Author's Name | Naoki Katoh |
| 2nd Author's Affiliation | University of Hyogo (Uoh) |
| 3rd Author's Name | Junichi Teruyama |
| 3rd Author's Affiliation | University of Hyogo (Uoh) |
| 4th Author's Name | Yuya Higashikawa |
| 4th Author's Affiliation | University of Hyogo (Uoh) |
| 5th Author's Name | |
| 5th Author's Affiliation | () |
| 6th Author's Name | |
| 6th Author's Affiliation | () |
| 7th Author's Name | |
| 7th Author's Affiliation | () |
| 8th Author's Name | |
| 8th Author's Affiliation | () |
| 9th Author's Name | |
| 9th Author's Affiliation | () |
| 10th Author's Name | |
| 10th Author's Affiliation | () |
| 11th Author's Name | |
| 11th Author's Affiliation | () |
| 12th Author's Name | |
| 12th Author's Affiliation | () |
| 13th Author's Name | |
| 13th Author's Affiliation | () |
| 14th Author's Name | |
| 14th Author's Affiliation | () |
| 15th Author's Name | |
| 15th Author's Affiliation | () |
| 16th Author's Name | |
| 16th Author's Affiliation | () |
| 17th Author's Name | |
| 17th Author's Affiliation | () |
| 18th Author's Name | |
| 18th Author's Affiliation | () |
| Speaker | Author-1 |
| Date Time | 2022-10-26 11:45:00 |
| Presentation Time | 30 minutes |
| Registration for | COMP |
| Paper # | COMP2022-15 |
| Volume (vol) | vol.122 |
| Number (no) | no.229 |
| Page | pp.7-13 |
| #Pages | 7 |
| Date of Issue | 2022-10-19 (COMP) |
[Return to Top Page]