Colorful Frontier-Based Search: Implicit Enumeration of Chordal and Interval Subgraphs
Colorful Frontier-Based Search: Implicit Enumeration of Chordal and Interval Subgraphs
复制标题
基于彩色前沿的搜索：弦和区间子图的隐式枚举
DOI：
10.1007/978-3-030-34029-2_9
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Yoshinaka Ryo
中科院分区：
文献类型：
--
作者：
Kawahara Jun;Saitoh Toshiki;Suzuki Hirofumi;Yoshinaka Ryo
本文考虑使用一种称为零抑制二元决策图（ZDD）的数据结构来枚举给定图的特定子图。一个ZDD可以非常复杂地表示解的集合。最近的研究表明，一种通常被称为基于前沿的搜索（FBS）的技术是一个强大的框架，用于使用ZDD枚举各种各样的但相当简单的子图类型。我们在本文中，提出了丰富多彩的FBS，FBS的增强，这使我们能够枚举更复杂的类型的子图比现有的FBS技术。在彩色FBS的基础上，我们设计了从输入图中构造表示弦子图和区间子图集合的ZDD的方法。计算机实验表明，所提出的方法运行速度比反向搜索的算法。
This paper considers enumeration of specific subgraphs of a given graph by using a data structure called a zero-suppressed binary decision diagram (ZDD). A ZDD can represent the set of solutions quite compactly. Recent studies have demonstrated that a technique generically called frontier-based search (FBS) is a powerful framework for using ZDDs to enumerate various yet rather simple types of subgraphs. We in this paper, propose colorful FBS, an enhancement of FBS, which enables us to enumerate more complex types of subgraphs than existing FBS techniques do. On the basis of colorful FBS, we design methods that construct ZDDs representing the sets of chordal and interval subgraphs from an input graph. Computer experiments show that the proposed methods run faster than reverse search based algorithms.