Title:
NETWORK DESIGN EVALUATION METHOD, NETWORK DESIGN EVALUATION DEVICE, AND PROGRAM
Document Type and Number:
WIPO Patent Application WO/2019/240043
Kind Code:
A1
Abstract:
The purpose of the present invention is to provide a network design evaluation method, a network design evaluation device, and a program provided with a ZDD algorithm for finding all edge-disjoint paths within a finite time from a given graph D. The network design evaluation method according to the present invention is designed to extract all paths for each of designated apex pairs from a given graph by a frontier method, express a path aggregate composed of the paths extracted for each apex pair as elements by a zero-suppressed binary decision diagram (ZDD), and perform Disjoint Join computation on all path aggregates expressed by the ZDD, thereby extracting edge-disjoint paths.
Inventors:
INOUE TAKERU (JP)
Application Number:
PCT/JP2019/022764
Publication Date:
December 19, 2019
Filing Date:
June 07, 2019
Export Citation:
Assignee:
NIPPON TELEGRAPH & TELEPHONE (JP)
International Classes:
G06N99/00; H04L45/128
Other References:
INOUE, T.: "Research Trends in ZDD and Frontier-based Search", THE JOURNAL OF THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS, vol. 101, no. 3, 1 March 2018 (2018-03-01), pages 297 - 301, ISSN: 0913-5693
KAWAHARA, J. ET AL.: "Solving the Longest Oneway- Ticket Problem and Enumerating Letter Graphs by Augmenting the Two Representative Approaches with ZDDs", COMPUTATIONAL INTELLIGENCE IN INFORMATION SYSTEMS (PROCEEDINGS OF CIIS 2016, 21 October 2016 (2016-10-21), pages 294 - 305, ISBN: 978-3-319-48516-4, Retrieved from the Internet
KAWAHARA, J. ET AL.: "Frontier-Based Search for Enumerating All Constrained Subgraphs with Compressed Representation", IEICE TRANSACTIONS ON FUNDAMENTALS, vol. E100-A, no. 9, 1 September 2017 (2017-09-01), pages 1773 - 1784, XP055662954, ISSN: 1745-1337
KAWAHARA, J. ET AL: "Enumerating Letter Graphs by Zero-suppressed Decision Diagrams", IEICE TECHNICAL REPORT, vol. 116, no. 116, 17 June 2016 (2016-06-17), pages 30 - 40, XP055662962, ISSN: 0913-5685
MIWA, H. ET AL., ALGORITHMS AND DATA STRUCTURES FOR OPTIMIZATION IN INFORMATION NETWORKS, 16 December 2015 (2015-12-16), pages 50 - 51, ISBN: 978-4-339-02802-7
INOUE, T .: "Reliability Analysis for Disjoint Paths", IEEE TRANSACTIONS ON RELIABILITY, vol. 68, no. 3, 1 September 2019 (2019-09-01), pages 985 - 998, XP011743153, ISSN: 0018-9529, DOI: 10.1109/TR.2018.2877775
KAWAHARA, J. ET AL.: "Solving the Longest Oneway- Ticket Problem and Enumerating Letter Graphs by Augmenting the Two Representative Approaches with ZDDs", COMPUTATIONAL INTELLIGENCE IN INFORMATION SYSTEMS (PROCEEDINGS OF CIIS 2016, 21 October 2016 (2016-10-21), pages 294 - 305, ISBN: 978-3-319-48516-4, Retrieved from the Internet
KAWAHARA, J. ET AL.: "Frontier-Based Search for Enumerating All Constrained Subgraphs with Compressed Representation", IEICE TRANSACTIONS ON FUNDAMENTALS, vol. E100-A, no. 9, 1 September 2017 (2017-09-01), pages 1773 - 1784, XP055662954, ISSN: 1745-1337
KAWAHARA, J. ET AL: "Enumerating Letter Graphs by Zero-suppressed Decision Diagrams", IEICE TECHNICAL REPORT, vol. 116, no. 116, 17 June 2016 (2016-06-17), pages 30 - 40, XP055662962, ISSN: 0913-5685
MIWA, H. ET AL., ALGORITHMS AND DATA STRUCTURES FOR OPTIMIZATION IN INFORMATION NETWORKS, 16 December 2015 (2015-12-16), pages 50 - 51, ISBN: 978-4-339-02802-7
INOUE, T .: "Reliability Analysis for Disjoint Paths", IEEE TRANSACTIONS ON RELIABILITY, vol. 68, no. 3, 1 September 2019 (2019-09-01), pages 985 - 998, XP011743153, ISSN: 0018-9529, DOI: 10.1109/TR.2018.2877775
Attorney, Agent or Firm:
OKADA, Kenji et al. (JP)
Download PDF: