Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs

DOI10.1137/S0097539792224814zbMath0918.68047OpenAlexW2006955534WikidataQ57535766 ScholiaQ57535766MaRDI QIDQ4229420

No author found.

Publication date: 22 February 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539792224814

zbMATH Keywords

graph theoryanalysis of algorithmsgraph partitioningchordal graphinterval graphmodular decompositiontransitive orientationtriangulated graphgraph recognitionsubstitution decompositioncardinality lexicographic orderingcycle-free poset

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (16)

Representing a concept lattice by a graph ⋮ Computing the clique-separator graph for an interval graph in linear time ⋮ A local approach to concept generation ⋮ Happy set problem on subclasses of co-comparability graphs ⋮ Organizing the atoms of the clique separator decomposition into an atom tree ⋮ Fully dynamic representations of interval graphs ⋮ A fully dynamic graph algorithm for recognizing interval graphs ⋮ Interval graph representation with given interval and intersection lengths ⋮ Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation ⋮ An implicit representation of chordal comparability graphs in linear time ⋮ Happy set problem on subclasses of co-comparability graphs ⋮ A simple algorithm to find Hamiltonian cycles in proper interval graphs ⋮ A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs ⋮ Construction of a simple elimination scheme for a chordal comparability graph in linear time ⋮ Modular decomposition and transitive orientation ⋮ Linear-time algorithms for tree root problems

This page was built for publication: Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs