Peng Li ; Yaokun Wu - A four-sweep LBFS recognition algorithm for interval graphs

dmtcs:2094 - Discrete Mathematics & Theoretical Computer Science, June 18, 2014, Vol. 16 no. 3 -
A four-sweep LBFS recognition algorithm for interval graphsArticle

Authors: Peng Li ORCID1; Yaokun Wu 1

  • 1 Department of mathematics and MOE-LSC

In their 2009 paper, Corneil et al. design a linear time interval graph recognition algorithm based on six sweeps of Lexicographic Breadth-First Search (LBFS) and prove its correctness. They believe that their corresponding 5-sweep LBFS interval graph recognition algorithm is also correct. Thanks to the LBFS structure theory established mainly by Corneil et al., we are able to present a 4-sweep LBFS algorithm which determines whether or not the input graph is a unit interval graph or an interval graph. Like the algorithm of Corneil et al., our algorithm does not involve any complicated data structure and can be executed in linear time.

Volume: Vol. 16 no. 3
Section: Graph Theory
Published on: June 18, 2014
Submitted on: December 4, 2011
Keywords: chordal graph,interval graph,interval representation,Lexicographic Breadth-First Search,perfect ordering,recognition algorithm,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 607 times.
This article's PDF has been downloaded 485 times.