| 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 | 2021-08-25 15:30 [Invited Talk] Transportation Problem on a Graph Allowing Sending and Bringing-back Tetsuo Asano (Kanazawa Univ.)  COMP2021-10 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | There are a number of problems classified as a transportation problem. In this paper we consider one of allowing sending and bringing-back commodities. Input is given as a weighted graph. Suppose amounts of supplies and demands are specified at each node and each node has one vehicle to carry commodities with bounded capacity. We want to see whether we can meet all demands by sending and bringing-back commodities. Cost is neglected. Unfortunately the problem is NP-complete for a general graph, but we present a polynomial-time algorithm for a graph containing a constant number of cycles. | |
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | transportation problem / algorithm / supply / demand / NP-complete / polynoial-time algorithm / / | |
| Reference Info. | IEICE Tech. Rep., vol. 121, no. 149, COMP2021-10, pp. 9-9, Aug. 2021. | |
| Paper # | COMP2021-10 | |
| Date of Issue | 2021-08-18 (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 | COMP2021-10 |
|
| Conference Information | |
| Committee | COMP IPSJ-AL |
| Conference Date | 2021-08-25 - 2021-08-26 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2021-08-COMP-AL |
| Language | Japanese |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Transportation Problem on a Graph Allowing Sending and Bringing-back |
| Sub Title (in English) | |
| Keyword(1) | transportation problem |
| Keyword(2) | algorithm |
| Keyword(3) | supply |
| Keyword(4) | demand |
| Keyword(5) | NP-complete |
| Keyword(6) | polynoial-time algorithm |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Tetsuo Asano |
| 1st Author's Affiliation | Kanazawa University (Kanazawa Univ.) |
| 2nd Author's Name | |
| 2nd Author's Affiliation | () |
| 3rd Author's Name | |
| 3rd Author's Affiliation | () |
| 4th Author's Name | |
| 4th Author's Affiliation | () |
| 5th Author's Name | |
| 5th Author's Affiliation | () |
| 6th Author's Name | |
| 6th Author's Affiliation | () |
| Speaker | Author-1 |
| Date Time | 2021-08-25 15:30:00 |
| Presentation Time | 60 minutes |
| Registration for | COMP |
| Paper # | COMP2021-10 |
| Volume (vol) | vol.121 |
| Number (no) | no.149 |
| Page | p.9 |
| #Pages | 1 |
| Date of Issue | 2021-08-18 (COMP) |
[Return to Top Page]