A Zero-Suppressed Binary Decision Diagram Approach for Constrained Path Enumeration

A Zero-Suppressed Binary Decision Diagram Approach for Constrained Path Enumeration

Combinatorial optimization over graphs has been the subject of research. Recently, the solution of such problems by enumeration using a compact data structure called the zero-suppressed binary decision diagram was proposed and studied. The paper augments the existing frontier-based search method of...

Full description

Saved in:
Bibliographic Details
Main Authors: Tan, Renzo Roel P, Kawahara, Jun, Garciano, Agnes, Sin, Immanuel
Format: text
Published: Archīum Ateneo 2019
Subjects:
zero-suppressed binary decision diagram
subgraph optimization
enumeration algorithm
Discrete Mathematics and Combinatorics
Mathematics
Online Access:https://archium.ateneo.edu/mathematics-faculty-pubs/195
https://archium.ateneo.edu/cgi/viewcontent.cgi?article=1198&context=mathematics-faculty-pubs
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Ateneo De Manila University
id ph-ateneo-arc.mathematics-faculty-pubs-1198
record_format eprints
spelling ph-ateneo-arc.mathematics-faculty-pubs-11982022-04-21T06:13:56Z A Zero-Suppressed Binary Decision Diagram Approach for Constrained Path Enumeration Tan, Renzo Roel P Kawahara, Jun Garciano, Agnes Sin, Immanuel Combinatorial optimization over graphs has been the subject of research. Recently, the solution of such problems by enumeration using a compact data structure called the zero-suppressed binary decision diagram was proposed and studied. The paper augments the existing frontier-based search method of construction and puts forth a technique for accommodating additional constraints during computation. The shortest and longest path problems for the Osaka Metro transit network are simultaneously solved as demonstration. Furthermore, a comparison of the approach with a conventional integer programming method is presented towards justifying the effectiveness of the algorithm. 2019-07-01T07:00:00Z text application/pdf https://archium.ateneo.edu/mathematics-faculty-pubs/195 https://archium.ateneo.edu/cgi/viewcontent.cgi?article=1198&context=mathematics-faculty-pubs Mathematics Faculty Publications Archīum Ateneo zero-suppressed binary decision diagram subgraph optimization enumeration algorithm Discrete Mathematics and Combinatorics Mathematics
institution Ateneo De Manila University
building Ateneo De Manila University Library
continent Asia
country Philippines
Philippines
content_provider Ateneo De Manila University Library
collection archium.Ateneo Institutional Repository
topic zero-suppressed binary decision diagram
subgraph optimization
enumeration algorithm
Discrete Mathematics and Combinatorics
Mathematics
spellingShingle zero-suppressed binary decision diagram
subgraph optimization
enumeration algorithm
Discrete Mathematics and Combinatorics
Mathematics
Tan, Renzo Roel P
Kawahara, Jun
Garciano, Agnes
Sin, Immanuel
A Zero-Suppressed Binary Decision Diagram Approach for Constrained Path Enumeration
description Combinatorial optimization over graphs has been the subject of research. Recently, the solution of such problems by enumeration using a compact data structure called the zero-suppressed binary decision diagram was proposed and studied. The paper augments the existing frontier-based search method of construction and puts forth a technique for accommodating additional constraints during computation. The shortest and longest path problems for the Osaka Metro transit network are simultaneously solved as demonstration. Furthermore, a comparison of the approach with a conventional integer programming method is presented towards justifying the effectiveness of the algorithm.
format text
author Tan, Renzo Roel P
Kawahara, Jun
Garciano, Agnes
Sin, Immanuel
author_facet Tan, Renzo Roel P
Kawahara, Jun
Garciano, Agnes
Sin, Immanuel
author_sort Tan, Renzo Roel P
title A Zero-Suppressed Binary Decision Diagram Approach for Constrained Path Enumeration
title_short A Zero-Suppressed Binary Decision Diagram Approach for Constrained Path Enumeration
title_full A Zero-Suppressed Binary Decision Diagram Approach for Constrained Path Enumeration
title_fullStr A Zero-Suppressed Binary Decision Diagram Approach for Constrained Path Enumeration
title_full_unstemmed A Zero-Suppressed Binary Decision Diagram Approach for Constrained Path Enumeration
title_sort zero-suppressed binary decision diagram approach for constrained path enumeration
publisher Archīum Ateneo
publishDate 2019
url https://archium.ateneo.edu/mathematics-faculty-pubs/195
https://archium.ateneo.edu/cgi/viewcontent.cgi?article=1198&context=mathematics-faculty-pubs
_version_ 1731309307631239168

Similar Items