TY - GEN

T1 - Solving the longest oneway-ticket problem and enumerating letter graphs by augmenting the two representative approaches with ZDDs

AU - Kawahara, Jun

AU - Saitoh, Toshiki

AU - Suzuki, Hirofumi

AU - Yoshinaka, Ryo

N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 2017

Y1 - 2017

N2 - Several researchers have studied subgraph enumeration algorithms that use a compressed expression for a family of sets, called a zero-suppressed binary decision diagram (ZDD), to solve subgraph optimization problems. We have two representative approaches to manipulate ZDDs effectively. One is fundamental mathematical operations on families of sets over ZDDs. The other is a direct construction method of a ZDD that represents desired subgraphs of a graph and is called frontierbased search. In this research, we augment the approaches by proposing two new operations, called disjoint join and joint join, on family algebra over ZDDs and extending the frontier-based search to enumerate subgraphs that have a given number of vertices of specified degrees. Employing the new approaches, we present enumeration algorithms for alphabet letter graphs on a given graph. Moreover, we solve a variant of the longest path problem, called the Longest Oneway-ticket Problem (LOP), that requires computing the longest trip on the railway network of the Japan Railways Group using a oneway ticket. Numerical experiments show that our algorithm solves the LOP and is faster than the existing integer programming approach for some instances.

AB - Several researchers have studied subgraph enumeration algorithms that use a compressed expression for a family of sets, called a zero-suppressed binary decision diagram (ZDD), to solve subgraph optimization problems. We have two representative approaches to manipulate ZDDs effectively. One is fundamental mathematical operations on families of sets over ZDDs. The other is a direct construction method of a ZDD that represents desired subgraphs of a graph and is called frontierbased search. In this research, we augment the approaches by proposing two new operations, called disjoint join and joint join, on family algebra over ZDDs and extending the frontier-based search to enumerate subgraphs that have a given number of vertices of specified degrees. Employing the new approaches, we present enumeration algorithms for alphabet letter graphs on a given graph. Moreover, we solve a variant of the longest path problem, called the Longest Oneway-ticket Problem (LOP), that requires computing the longest trip on the railway network of the Japan Railways Group using a oneway ticket. Numerical experiments show that our algorithm solves the LOP and is faster than the existing integer programming approach for some instances.

UR - http://www.scopus.com/inward/record.url?scp=84994827378&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84994827378&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-48517-1_26

DO - 10.1007/978-3-319-48517-1_26

M3 - Conference contribution

AN - SCOPUS:84994827378

SN - 9783319485164

T3 - Advances in Intelligent Systems and Computing

SP - 294

EP - 305

BT - Computational Intelligence in Information Systems - Proceedings of the Computational Intelligence in Information Systems Conference, CIIS 2016

A2 - Phon-Amnuaisuk, Somnuk

A2 - Au, Thien-Wan

A2 - Omar, Saiful

PB - Springer Verlag

T2 - International Conference on Computational Intelligence in Information Systems, CIIS 2016

Y2 - 18 November 2016 through 20 November 2016

ER -