On the interval completion of chordal graphs

DOI10.1016/J.DAM.2005.09.010zbMath1159.05049OpenAlexW1991485710MaRDI QIDQ2492201

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 graphsstarlike graphsPathwidthChordal graphsinterval completionThreshold completion

Mathematics Subject Classification ID

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

Related Items (5)

Mixed Search Number and Linear-Width of Interval and Split Graphs ⋮ Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs ⋮ 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 ⋮ On the proper interval completion problem within some chordal subclasses

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Interval graphs and searching
• The splittance of a graph
• Graph minors. X: Obstructions to tree-decomposition
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the pathwidth of chordal graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph searching on some subclasses of chordal graphs
• Triangulating graphs without asteroidal triples
• Incidence matrices, interval graphs and seriation in archeology
• Graph Searching and Interval Completion
• Representation of a finite graph by a set of intervals on the real line
• The Complexity of the Partial Order Dimension Problem
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Computing the Minimum Fill-In is NP-Complete
• Treewidth and Minimum Fill-in on d-Trapezoid Graphs
• Graph Classes: A Survey
• Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
• The Profile Minimization Problem in Trees
• Mapping the genome
• A Characterization of Comparability Graphs and of Interval Graphs

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