On listing, sampling, and counting the chordal graphs with edge constraints

DOI10.1016/J.TCS.2010.03.024MaRDI QIDQ974754zbMATH OpenOpenAlexFDO

Authors Shuji Kijima, Masashi Kiyomi, Yoshio Okamoto, Takeaki Uno

Publication date 7 June 2010

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.03.024

zbMATH Keywords

\#P-completenesschordal completion/deletionenumerationgraph sandwichMarkov chain Monte Carlo

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• Counting the number of independent sets in chordal graphs
• Counting the number of matchings in chordal and chordal bipartite graph classes
• Graph-Theoretic Concepts in Computer Science
• Linear-time generation of random chordal graphs

Cites work

• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• Algorithmic Aspects of Vertex Elimination on Graphs
• Characterizing Minimal Interval Completions
• Chordal Deletion Is Fixed-Parameter Tractable
• Complexity classification of some edge modification problems
• Computing the Minimum Fill-In is NP-Complete
• Counting labelled chordal graphs
• Exact Algorithms for Treewidth and Minimum Fill-In
• Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
• Fully dynamic algorithms for chordal graphs and split graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Graph Sandwich Problems
• scientific article; zbMATH DE number 420886 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4211299 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• Incidence matrices and interval graphs
• Listing Chordal Graphs and Interval Graphs
• Minimal triangulations of graphs: a survey
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• On rigid circuit graphs
• Representation of a finite graph by a set of intervals on the real line
• Reverse search for enumeration
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Sparse quasi-Newton updates with positive definite matrix completion
• The Complexity of Enumeration and Reliability Problems

Cited in

(1)

• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints

This page was built for publication: On listing, sampling, and counting the chordal graphs with edge constraints

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