Computing the clique-separator graph for an interval graph in linear time

DOI10.1016/J.IPL.2017.04.007MaRDI QIDQ2628270zbMATH OpenOpenAlexFDO

Authors Louis Ibarra

Publication date 13 June 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2017.04.007

zbMATH Keywords

chordal graphsgraph algorithmsinterval graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The clique-separator graph for chordal graphs
• scientific article; zbMATH DE number 4049085
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• A fully dynamic graph algorithm for recognizing interval graphs
• A linear-time algorithm for proper interval graph recognition

Cites work

• A fully dynamic graph algorithm for recognizing interval graphs
• Algorithmic graph theory and perfect graphs
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Counting clique trees and computing perfect elimination schemes in parallel
• Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs
• Graph Classes: A Survey
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• Incidence matrices and interval graphs
• Introduction to algorithms.
• PC trees and circular-ones arrangements.
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The clique-separator graph for chordal graphs
• The LBFS structure and recognition of interval graphs
• The NP-completeness column: an ongoing guide
• Topics in Intersection Graph Theory

Cited in

(3)

• Clique partitioning of interval graphs with submodular costs on the cliques
• A linear time algorithm to compute square of interval graphs and their colouring
• Algorithms – ESA 2005

This page was built for publication: Computing the clique-separator graph for an interval graph in linear time

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