Geodesic
Maximal Neighborhood Search and Rigid Interval Graphs
Journal of Graph Algorithms and Applications, Tome 17 (2013) no. 3, pp. 245-264.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

A rigid interval graph is an interval graph which has only one clique tree. In 2009, Panda and Das show that all connected unit interval graphs are rigid interval graphs. Generalizing the two classic graph search algorithms, Lexicographic Breadth-First Search (LBFS) and Maximum Cardinality Search (MCS), Corneil and Krueger propose in 2008 the so-called Maximal Neighborhood Search (MNS) and show that one sweep of MNS is enough to recognize chordal graphs. We develop the MNS properties of rigid interval graphs and characterize this graph class in several different ways. This allows us obtain several linear time multi-sweep MNS algorithms for recognizing rigid interval graphs and unit interval graphs, generalizing a corresponding 3-sweep LBFS algorithm for unit interval graph recognition designed by Corneil in 2004. For unit interval graphs, we even present a new linear time 2-sweep MNS certifying recognition algorithm. An erratum for this paper has been published on October 2013 (see link on the right) 
@article{JGAA_2013_17_3_a4,
     author = {Peng Li and Yaokun Wu},
     title = {Maximal {Neighborhood}  {Search} and {Rigid} {Interval} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {245--264},
     publisher = {mathdoc},
     volume = {17},
     number = {3},
     year = {2013},
     doi = {10.7155/jgaa.00293},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00293/}
}
TY  - JOUR
AU  - Peng Li
AU  - Yaokun Wu
TI  - Maximal Neighborhood  Search and Rigid Interval Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2013
SP  - 245
EP  - 264
VL  - 17
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00293/
DO  - 10.7155/jgaa.00293
LA  - en
ID  - JGAA_2013_17_3_a4
ER  - 
%0 Journal Article
%A Peng Li
%A Yaokun Wu
%T Maximal Neighborhood  Search and Rigid Interval Graphs
%J Journal of Graph Algorithms and Applications
%D 2013
%P 245-264
%V 17
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00293/
%R 10.7155/jgaa.00293
%G en
%F JGAA_2013_17_3_a4
Peng Li; Yaokun Wu. Maximal Neighborhood  Search and Rigid Interval Graphs. Journal of Graph Algorithms and Applications, Tome 17 (2013) no. 3, pp. 245-264. doi : 10.7155/jgaa.00293. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00293/

Cité par Sources :