Maximal Neighborhood Search and Rigid Interval Graphs | Zendy

Peng Li | Zendy; Yaokun Wu | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Maximal Neighborhood Search and Rigid Interval Graphs

Author(s) -

Peng Li,

Yaokun Wu

Publication year - 2013

Publication title -

journal of graph algorithms and applications

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.387

H-Index - 38

ISSN - 1526-1719

DOI - 10.7155/jgaa.00293

Subject(s) - interval (graph theory) , combinatorics , mathematics , computer science , interval graph , chordal graph , graph , 1 planar graph

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research