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

DOI10.1007/978-3-540-69733-6_45zbMath1148.68419OpenAlexW1592286926MaRDI QIDQ3511357

Takeaki Uno, Shuji Kijima, Masashi Kiyomi, Yoshio Okamoto

Publication date: 10 July 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69733-6_45

Mathematics Subject Classification ID

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

Related Items

Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone ⋮ Strongly chordal and chordal bipartite graphs are sandwich monotone ⋮ On listing, sampling, and counting the chordal graphs with edge constraints ⋮ Structural Markov graph laws for Bayesian model uncertainty

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• 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
• Chordal Deletion Is Fixed-Parameter Tractable
• Listing Chordal Graphs and Interval Graphs
• Characterizing Minimal Interval Completions
• 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
• Automata, Languages and Programming
• Complexity classification of some edge modification problems