Title of article
A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs Original Research Article
Author/Authors
Derek G. Corneil، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2004
Pages
9
From page
371
To page
379
Abstract
We present a simple linear time algorithm for unit interval graph recognition. This algorithm uses 3 LBFS sweeps and then a very simple test to determine if the given graph is a unit interval graph. It is argued that this algorithm is the most easily implementable unit interval graph recognition algorithm known.
Keywords
Unit interval graphs , Proper interval graphs , Graph recognition algorithm , Lexicographic breadth first search
Journal title
Discrete Applied Mathematics
Serial Year
2004
Journal title
Discrete Applied Mathematics
Record number
885853
Link To Document