A new LBFS-based algorithm for cocomparability graph recognition

详细信息    查看全文

• 作者：Jé ; ré ; mie Dusart ^{dusart@liafa.univ-paris-diderot.fr} ; Michel Habib ; ^{habib@liafa.univ-paris-diderot.fr}
• 关键词：Cocomparability and comparability graphs ; Graph search LBFS and LBFS+ ; Transitive orientation
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P1
• 页码：149-161
• 全文大小：625 K
• 卷排序：216

文摘

How much can you learn about the structure of a given graph, using a series of successive graph searches? We consider here cocomparability graphs which are the complement of the graphs that admit a transitive orientation (comparability graphs). We study the use of a series of successive LBFS searches in order to capture the structure of these graphs. On cocomparability graphs many problems like coloring, Hamilton path, maximal clique which are NP-complete in the general case can be solved in polynomial time. For all those problems a decisive step is to find a cocomp ordering. We will prove the correctness of an algorithm to find a cocomp ordering using |V(G)||V(G)| successive LBFS. Our main result answers a question asked in Corneil, Olariu and Stewart [2009] about the existence of a multisweep LBFS algorithm for cocomparability graphs, and lays the foundation of a simple linear time multisweep LBFS algorithm to find a cocomp ordering.