On the interval completion of chordal graphs

DOI10.1016/J.DAM.2005.09.010zbMATH Open1159.05049OpenAlexW1991485710MaRDI QIDQ2492201FDOQ2492201

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

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

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)

Cites Work

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

Cited In (10)

• Title not available (Why is that?)
• 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
• 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
• Title not available (Why is that?)
• 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)