An integer programming model for the minimum interval graph completion problem

DOI10.1016/J.ENDM.2010.05.074MaRDI QIDQ2883618zbMATH OpenOpenAlexFDO

Authors Isabel Cristina Lopes, José Valério de Carvalho

Publication date 13 May 2012

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2010.05.074

zbMATH Keywords

interval graphminimum fill-inminimum interval completion

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• Algorithms – ESA 2005
• Minimal Interval Completion Through Graph Exploration
• Minimal interval completion through graph exploration
• An \({\mathcal{O}}(n^2)\)-time algorithm for the minimal interval completion problem
• An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
• Incidence matrices, interval graphs and seriation in archeology
• Minimal comparability completions of arbitrary graphs
• Minimal split completions
• Minimal triangulations of graphs: a survey
• On the complexity of DNA physical mapping
• On the homogeneous representation of interval graphs
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• Profile minimization problem for matrices and graphs

Cited in

(2)

• Minimal interval completion through graph exploration
• Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles

This page was built for publication: An integer programming model for the minimum interval graph completion problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2883618)