Colorful Frontier-Based Search: Implicit Enumeration of Chordal and Interval Subgraphs

Jun Kawahara, Toshiki Saitoh, Hirofumi Suzuki, Ryo Yoshinaka

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationAnalysis of Experimental Algorithms - Special Event,SEA² 2019, Revised Selected Papers
EditorsIlias Kotsireas, Panos Pardalos, Arsenis Tsokas, Konstantinos E. Parsopoulos, Dimitris Souravlias
Number of pages17
ISBN (Print)9783030340285
Publication statusPublished - 2019
EventSpecial Event on Analysis of Experimental Algorithms, SEA² 2019 - Kalamata, Greece
Duration: 2019 Jun 242019 Jun 29

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11544 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceSpecial Event on Analysis of Experimental Algorithms, SEA² 2019


  • Chordal graph
  • Decision diagram
  • Frontier-based search
  • Graph algorithm
  • Graph enumeration
  • Interval graph


Dive into the research topics of 'Colorful Frontier-Based Search: Implicit Enumeration of Chordal and Interval Subgraphs'. Together they form a unique fingerprint.

Cite this