Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs

DOI10.1016/j.dam.2004.10.001zbMath1077.68076OpenAlexW2057990760MaRDI QIDQ1763474

Daniel Meister

Publication date: 22 February 2005

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2004.10.001

zbMATH Keywords

BandwidthInterval graphsProper interval graphsAT-free claw-free graphsCo-comparability graphsMinimal triangulationsPartition refinement

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (15)

Two characterisations of the minimal triangulations of permutation graphs ⋮ Organizing the atoms of the clique separator decomposition into an atom tree ⋮ A tie-break model for graph search ⋮ Certifying algorithms ⋮ A certifying and dynamic algorithm for the recognition of proper circular-arc graphs ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ Treewidth and minimum fill-in on permutation graphs in linear time ⋮ Hardness and approximation of minimum distortion embeddings ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions ⋮ Minimal interval completion through graph exploration ⋮ Bandwidth of Bipartite Permutation Graphs in Polynomial Time ⋮ A new representation of proper interval graphs with an application to clique-width ⋮ Bandwidth of bipartite permutation graphs in polynomial time ⋮ Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for proper interval graph recognition
• Simple linear time recognition of unit interval graphs
• On rigid circuit graphs
• Tolerance graphs
• An optimal greedy heuristic to color interval graphs
• A linear time recognition algorithm for proper interval graphs
• The NP-completeness of the bandwidth minimization problem
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Modular decomposition and transitive orientation
• Characterizations and algorithmic applications of chordal graph embeddings
• Separability generalizes Dirac's theorem
• Interval degree and bandwidth of a graph
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• A practical algorithm for making filled graphs minimal
• On claw-free asteroidal triple-free graphs
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Triangulating graphs without asteroidal triples
• Optimal greedy algorithms for indifference graphs
• Incidence matrices and interval graphs
• Triangulated graphs and the elimination process
• Domination on Cocomparability Graphs
• Representation of a finite graph by a set of intervals on the real line
• Three Partition Refinement Algorithms
• An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
• Computing the Minimum Fill-In is NP-Complete
• Algorithmic Aspects of Vertex Elimination on Graphs
• Complexity Results for Bandwidth Minimization
• Software reliability via run-time result-checking
• Graph Classes: A Survey
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
• Asteroidal Triple-Free Graphs
• Approximating the Bandwidth for Asteroidal Triple-Free Graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Fully dynamic algorithms for chordal graphs and split graphs
• Minimal elimination of planar graphs
• Transitiv orientierbare Graphen
• Graph-Theoretic Concepts in Computer Science
• Minimal elimination ordering for graphs of bounded degree
• Approximating the bandwidth for asteroidal triple-free graphs

This page was built for publication: Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs