Efficiently enumerating minimal triangulations

DOI10.1016/j.dam.2020.05.034zbMath1472.05070OpenAlexW3036666109MaRDI QIDQ1983135

Batya Kenig, Benny Kimelfeld, Markus Kröll, Nofar Carmeli

Publication date: 15 September 2021

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

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

zbMATH Keywords

tree decompositionmaximal cliquesmaximal independent setsminimal triangulationminimal separatorsenumeration algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (2)

Proximity Search for Maximal Subgraph Enumeration ⋮ Enumerating teams in first-order team logics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hypertree decompositions and tractable queries
• On rigid circuit graphs
• Graph minors. III. Planar tree-width
• Minimal triangulations of graphs: a survey
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• On generating all maximal independent sets
• Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
• Minimal vertex separators of chordal graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• On treewidth and minimum fill-in of asteroidal triple-free graphs
• A practical algorithm for making filled graphs minimal
• Conjunctive-query containment and constraint satisfaction
• Reverse search for enumeration
• Triangulated graphs and the elimination process
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Minimal Orderings Revisited
• Listing all the minimum spanning trees in an undirected graph
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Generalized hypertree decompositions: NP-hardness and tractable variants
• Complexity of Finding Embeddings in a k-Tree
• Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
• Computing the Minimum Fill-In is NP-Complete
• Graph Sandwich Problems
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• New polynomial delay bounds for maximal subgraph enumeration by proximity search
• Algorithms – ESA 2004
• A wide-range algorithm for minimal triangulation from an arbitrary ordering
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Efficiently enumerating minimal triangulations