Minimal proper interval completions
type: Item
instance of: scholarly article
title: Minimal proper interval completions
zbMATH Open document ID: 1185.05107
author: Ivan Rapaport
author: Karol Suchan
author: Ioan Todinca
published in: Information Processing Letters
publication date: 2010-04-19T00:00:00Z
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5694932
zbMATH Keywords: graph algorithms
zbMATH Keywords: proper interval graphs
zbMATH Keywords: minimal proper interval completions
zbMATH Keywords: bandwidth
Wikidata QID: Q62046062
MaRDI profile type: Publication
full work available at URL: j.ipl.2007.11.013
OpenAlex ID: W2159194941
cites work: Separability generalizes Dirac's theorem
cites work: Fixed-Parameter Tractability and Completeness I: Basic Results
cites work: Betweenness, orders and interval graphs
cites work: Algorithmic graph theory and perfect 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: Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions
cites work: Algorithms – ESA 2005
cites work: Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
cites work: Q3481747
cites work: Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
cites work: Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
cites work: Minimal fill in O(\(n^{2.69}\)) time
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
cites work: A linear time recognition algorithm for proper interval graphs
DBLP publication ID: journals/ipl/RapaportST08
DOI: 10.1016/J.IPL.2007.11.013
Recommended article: Minimal Proper Interval Completions
Recommended article: Algorithms – ESA 2005
Recommended article: Q3527497
Recommended article: Q3975929
Recommended article: Minimal pairs and complete problems
Recommended article: Minimal split completions
Recommended article: Minimality and completions of PA
Recommended article: Q3360916
Recommended article: Minimal quasi-complete intersection ideals
Recommended article: Tightly bounded completions
description: scientific article; zbMATH DE number 5694932