Minimal interval completion through graph exploration
type: Item
instance of: scholarly article
title: Minimal interval completion through graph exploration
zbMATH Open document ID: 1161.05052
author: Karol Suchan
author: Ioan Todinca
published in: Theoretical Computer Science
publication date: 2009-02-19T00:00:00Z
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5509586
zbMATH Keywords: interval graph
zbMATH Keywords: minimal interval completion
MaRDI profile type: Publication
full work available at URL: j.tcs.2008.09.053
OpenAlex ID: W1982692675
Wikidata QID: Q62046056
cites work: Separability generalizes Dirac's theorem
cites work: Treewidth: Structure and Algorithms
cites work: Q4198056
cites work: A Characterization of Comparability Graphs and of Interval Graphs
cites work: Q3328583
cites work: On the pathwidth of chordal graphs
cites work: PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
cites work: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
cites work: Minimal Split Completions of Graphs
cites work: Minimal comparability completions of arbitrary graphs
cites work: Algorithms – ESA 2005
cites work: Computing minimal triangulations in time \(O(n^{\alpha \log n}) = o(n^{2.376})\)
cites work: Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
cites work: On minimal augmentation of a graph to obtain an interval graph
cites work: An optimal greedy heuristic to color interval graphs
cites work: Minimal Proper Interval Completions
DOI: 10.1016/J.TCS.2008.09.053
DBLP publication ID: journals/tcs/SuchanT09
Recommended article: Minimal Interval Completion Through Graph Exploration
Recommended article: Graph searching and interval completion
Recommended article: An integer programming model for the minimum interval graph completion problem
Recommended article: Q4232802
Recommended article: Algorithms – ESA 2005
Recommended article: Q3405110
Recommended article: Optimal constrained graph exploration
Recommended article: On representing an interval graph using the minimum number of interval lengths
Recommended article: Characterizing and computing minimal cograph completions
description: scientific article; zbMATH DE number 5509586