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

DOI10.1016/J.DAM.2004.10.001MaRDI QIDQ1763474zbMATH OpenOpenAlexFDO

Authors 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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• Maximum cardinality search for computing minimal triangulations of graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• Approximating the treewidth of AT-free graphs.
• scientific article; zbMATH DE number 1953077
• A wide-range algorithm for minimal triangulation from an arbitrary ordering

Cites work

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

Cited in

(18)

• Hardness and approximation of minimum distortion embeddings
• Treewidth and minimum fill-in on permutation graphs in linear time
• Organizing the atoms of the clique separator decomposition into an atom tree
• 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
• Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
• On the power of graph searching for cocomparability graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• Graphs with at most two moplexes
• A certifying and dynamic algorithm for the recognition of proper circular-arc graphs
• Triangulation and clique separator decomposition of claw-free graphs
• A tie-break model for graph search
• Bandwidth of Bipartite Permutation Graphs in Polynomial Time
• Certifying algorithms
• Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications
• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• Two characterisations of the minimal triangulations of permutation graphs

Describes a project that uses

Uses Software

• LEDA

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

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