Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
type: Item
instance of: scholarly article
title: Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
zbMATH Open document ID: 1077.68076
author: Daniel Meister
published in: Discrete Applied Mathematics
publication date: 2005-02-22T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C78
zbMATH DE Number: 2136332
zbMATH Keywords: Partition refinement
zbMATH Keywords: Interval graphs
zbMATH Keywords: Proper interval graphs
zbMATH Keywords: Minimal triangulations
zbMATH Keywords: AT-free claw-free graphs
zbMATH Keywords: Co-comparability graphs
zbMATH Keywords: Bandwidth
describes a project that uses: LEDA
MaRDI profile type: Publication
full work available at URL: j.dam.2004.10.001
OpenAlex ID: W2057990760
cites work: Q4252378
cites work: Q4414480
cites work: Separability generalizes Dirac's theorem
cites work: A practical algorithm for making filled graphs minimal
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Graph Classes: A Survey
cites work: Graph-Theoretic Concepts in Computer Science
cites work: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
cites work: Simple linear time recognition of unit interval graphs
cites work: Asteroidal Triple-Free Graphs
cites work: Q4250178
cites work: Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
cites work: Q4373676
cites work: Minimal elimination of planar graphs
cites work: Minimal elimination ordering for graphs of bounded degree
cites work: Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
cites work: On rigid circuit graphs
cites work: Interval degree and bandwidth of a graph
cites work: Incidence matrices and interval graphs
cites work: Transitiv orientierbare Graphen
cites work: Complexity Results for Bandwidth Minimization
cites work: Q3328583
cites work: Tolerance graphs
cites work: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
cites work: On claw-free asteroidal triple-free graphs
cites work: A linear-time algorithm for proper interval graph recognition
cites work: Fully dynamic algorithms for chordal graphs and split graphs
cites work: Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
cites work: Approximating the bandwidth for asteroidal triple-free graphs
cites work: Approximating the Bandwidth for Asteroidal Triple-Free Graphs
cites work: An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
cites work: Q4471290
cites work: Domination on Cocomparability Graphs
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Optimal greedy algorithms for indifference graphs
cites work: Modular decomposition and transitive orientation
cites work: Q4702188
cites work: Triangulating graphs without asteroidal triples
cites work: An optimal greedy heuristic to color interval graphs
cites work: Three Partition Refinement Algorithms
cites work: A linear time recognition algorithm for proper interval graphs
cites work: The NP-completeness of the bandwidth minimization problem
cites work: Characterizations and algorithmic applications of chordal graph embeddings
cites work: Q5588432
cites work: Triangulated graphs and the elimination process
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
cites work: Software reliability via run-time result-checking
cites work: Computing the Minimum Fill-In is NP-Complete
DOI: 10.1016/J.DAM.2004.10.001
description: scientific article; zbMATH DE number 2136332