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

DOI10.1016/j.tcs.2010.03.024zbMath1209.68377OpenAlexW2066133611MaRDI QIDQ974754

Yoshio Okamoto, Shuji Kijima, Takeaki Uno, Masashi Kiyomi

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

Markov chain Monte Carloenumeration\#P-completenesschordal completion/deletiongraph sandwich

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Minimal triangulations of graphs: a survey
• Sparse quasi-Newton updates with positive definite matrix completion
• Counting labelled chordal graphs
• Reverse search for enumeration
• Incidence matrices and interval graphs
• Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
• Representation of a finite graph by a set of intervals on the real line
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
• Chordal Deletion Is Fixed-Parameter Tractable
• Listing Chordal Graphs and Interval Graphs
• Characterizing Minimal Interval Completions
• Exact Algorithms for Treewidth and Minimum Fill-In
• Graph minors. II. Algorithmic aspects of tree-width
• The Complexity of Enumeration and Reliability Problems
• Computing the Minimum Fill-In is NP-Complete
• Algorithmic Aspects of Vertex Elimination on Graphs
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• Graph Sandwich Problems
• Fully dynamic algorithms for chordal graphs and split graphs
• Complexity classification of some edge modification problems