On listing, sampling, and counting the chordal graphs with edge constraints
type: Item
instance of: scholarly article
title: On listing, sampling, and counting the chordal graphs with edge constraints
zbMATH Open document ID: 1209.68377
author: Shuji Kijima
author: Masashi Kiyomi
author: Yoshio Okamoto
author: Takeaki Uno
published in: Theoretical Computer Science
publication date: 2010-06-07T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 5717741
zbMATH Keywords: graph sandwich
zbMATH Keywords: chordal completion/deletion
zbMATH Keywords: enumeration
zbMATH Keywords: \#P-completeness
zbMATH Keywords: Markov chain Monte Carlo
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.03.024
OpenAlex ID: W2066133611
cites work: Reverse search for enumeration
cites work: On rigid circuit graphs
cites work: Incidence matrices and interval graphs
cites work: Exact Algorithms for Treewidth and Minimum Fill-In
cites work: Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
cites work: Q3328583
cites work: Graph Sandwich Problems
cites work: Minimal triangulations of graphs: a survey
cites work: Characterizing Minimal Interval Completions
cites work: Fully dynamic algorithms for chordal graphs and split graphs
cites work: On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
cites work: Listing Chordal Graphs and Interval Graphs
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Chordal Deletion Is Fixed-Parameter Tractable
cites work: A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
cites work: Complexity classification of some edge modification problems
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Q5683627
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: Q3135094
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Sparse quasi-Newton updates with positive definite matrix completion
cites work: Computing the Minimum Fill-In is NP-Complete
cites work: Q3358073
cites work: Counting labelled chordal graphs
DOI: 10.1016/J.TCS.2010.03.024
description: scientific article; zbMATH DE number 5717741