| 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 | 2023-03-02 11:00 Finding Forcing on ZDD by Dynamic Programming Takashi Harada, Shogo Takeuchi (Kochi Univ. of Tech.)  COMP2022-33 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | Exact cover problem takes a set S and a subset F of the power set of S as an input and determines whether there exists a subset of F that is a partition of S. Combinatorial problems such as graph coloring and vehicle routing as well as puzzles such as sudoku and polyomino can be formulated as an exact cover problem. Since the size of a practical instance can be large, an algorithm that takes an input as zero-suppressed binary decision diagram (ZDD) was proposed. An instance can be transformed into a simpler one based on a binary relation on S called Forcing. In this paper, we propose an algorithm for finding Forcing on ZDD by dynamic programming. | |
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | exact cover problem / DLX / ZDD / D3X / dynamic programming / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 122, no. 414, COMP2022-33, pp. 1-6, March 2023. | |
| Paper # | COMP2022-33 | |
| Date of Issue | 2023-02-23 (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-33 |
|
| Conference Information | |
| Committee | COMP |
| Conference Date | 2023-03-02 - 2023-03-02 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Ochanomizu University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Theoretical Computer Science, etc |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2023-03-COMP |
| Language | Japanese |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Finding Forcing on ZDD by Dynamic Programming |
| Sub Title (in English) | |
| Keyword(1) | exact cover problem |
| Keyword(2) | DLX |
| Keyword(3) | ZDD |
| Keyword(4) | D3X |
| Keyword(5) | dynamic programming |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Takashi Harada |
| 1st Author's Affiliation | Kochi University of Technology (Kochi Univ. of Tech.) |
| 2nd Author's Name | Shogo Takeuchi |
| 2nd Author's Affiliation | Kochi University of Technology (Kochi Univ. of Tech.) |
| 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 | 2023-03-02 11:00:00 |
| Presentation Time | 30 minutes |
| Registration for | COMP |
| Paper # | COMP2022-33 |
| Volume (vol) | vol.122 |
| Number (no) | no.414 |
| Page | pp.1-6 |
| #Pages | 6 |
| Date of Issue | 2023-02-23 (COMP) |
[Return to Top Page]