Efficiently enumerating minimal triangulations
type: Item
instance of: scholarly article
title: Efficiently enumerating minimal triangulations
zbMATH Open document ID: 1472.05070
author: Nofar Carmeli
author: Batya Kenig
author: Benny Kimelfeld
author: Markus Kröll
published in: Discrete Applied Mathematics
publication date: 2021-09-15T00:00:00Z
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7395742
zbMATH Keywords: minimal triangulation
zbMATH Keywords: tree decomposition
zbMATH Keywords: enumeration algorithm
zbMATH Keywords: minimal separators
zbMATH Keywords: maximal independent sets
zbMATH Keywords: maximal cliques
MaRDI profile type: Publication
full work available at URL: j.dam.2020.05.034
OpenAlex ID: W3036666109
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Reverse search for enumeration
cites work: Q4414480
cites work: Q4944976
cites work: A wide-range algorithm for minimal triangulation from an arbitrary ordering
cites work: A practical algorithm for making filled graphs minimal
cites work: Q3169431
cites work: Algorithms – ESA 2004
cites work: Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
cites work: Listing Maximal Independent Sets with Minimal Space and Bounded Delay
cites work: New polynomial delay bounds for maximal subgraph enumeration by proximity search
cites work: Q4373676
cites work: On rigid circuit graphs
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Q3328583
cites work: Graph Sandwich Problems
cites work: Q5715720
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Hypertree decompositions and tractable queries
cites work: Generalized hypertree decompositions: NP-hardness and tractable variants
cites work: Minimal triangulations of graphs: a survey
cites work: On generating all maximal independent sets
cites work: On treewidth and minimum fill-in of asteroidal triple-free graphs
cites work: Conjunctive-query containment and constraint satisfaction
cites work: Minimal vertex separators of chordal graphs
cites work: Q4734791
cites work: Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
cites work: Approximating fractional hypertree width
cites work: Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
cites work: Characterizations and algorithmic applications of chordal graph embeddings
cites work: Minimal orderings revisited
cites work: Graph minors. III. Planar tree-width
cites work: Triangulated graphs and the elimination process
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: Listing all the minimum spanning trees in an undirected graph
cites work: Computing the Minimum Fill-In is NP-Complete
DOI: 10.1016/J.DAM.2020.05.034
description: scientific article; zbMATH DE number 7395742