An <i>O</i>(<i>n</i><SUP>2</SUP>)-time algorithm for the minimal interval completion problem

作     者：Crespelle, Christophe Todinca, Loan 

作者机构：Univ Lyon 1 D NET INRIA LIP CNRSENS Lyon F-69622 Villeurbanne France Univ Orleans LIFO F-45067 Orleans 2 France 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 

年 卷 期：2013年第494卷

页      面：75-85页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Graph algorithms Interval graphs Minimal interval completions 

摘      要：An interval completion of an arbitrary graph G is an interval graph H, on the same vertex set, obtained from G by adding new edges. If the set of newly added edges is inclusion-minimal among all possibilities, we say that H is a minimal interval completion of G. We give an O(n(2))-time algorithm to obtain a minimal interval completion of an arbitrary graph. This improves the previous O(nm) time bound for the problem and lowers this bound for the first time below the best known bound for minimal chordal completion. (c) 2013 Elsevier B.V. All rights reserved.