On the interval completion of chordal graphs

DOI10.1016/J.DAM.2005.09.010MaRDI QIDQ2492201zbMATH OpenOpenAlexFDO

Authors Sheng-Lung Peng, Chi-Kang Chen

Publication date 9 June 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.09.010

zbMATH Keywords

graph algorithmssplit graphsPathwidthChordal graphsstarlike graphsinterval completionThreshold completion

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Chordal completions of planar graphs
• On the interval number of a chordal graph
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• scientific article; zbMATH DE number 867646
• scientific article; zbMATH DE number 1185294
• scientific article; zbMATH DE number 431510
• The interval graph completion problem for the complete multipartite graphs
• scientific article; zbMATH DE number 1286524
• scientific article; zbMATH DE number 5059933
• Matrix completions and chordal graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 176249 (Why is no real title available?)
• scientific article; zbMATH DE number 176780 (Why is no real title available?)
• scientific article; zbMATH DE number 177539 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1261808 (Why is no real title available?)
• scientific article; zbMATH DE number 1293767 (Why is no real title available?)
• scientific article; zbMATH DE number 1303559 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Computing the Minimum Fill-In is NP-Complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph Classes: A Survey
• Graph minors. X: Obstructions to tree-decomposition
• Graph searching and interval completion
• Graph searching on some subclasses of chordal graphs
• Incidence matrices, interval graphs and seriation in archeology
• Interval graphs and searching
• Mapping the genome
• On the pathwidth of chordal graphs
• Representation of a finite graph by a set of intervals on the real line
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Complexity of the Partial Order Dimension Problem
• The Profile Minimization Problem in Trees
• The splittance of a graph
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Triangulating graphs without asteroidal triples

Cited in

(10)

• scientific article; zbMATH DE number 5059933 (Why is no real title available?)
• scientific article; zbMATH DE number 5671249 (Why is no real title available?)
• On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
• Some completion problems for graphs without chordless cycles of prescribed lengths
• The interval graph completion problem for the complete multipartite graphs
• On the proper interval completion problem within some chordal subclasses
• Mixed search number and linear-width of interval and split graphs
• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• Mixed Search Number and Linear-Width of Interval and Split Graphs
• Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs

This page was built for publication: On the interval completion of chordal graphs

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