Counting the number of independent sets in chordal graphs
type: Item
instance of: scholarly article
title: Counting the number of independent sets in chordal graphs
zbMATH Open document ID: 1146.05029
author: Yoshio Okamoto
author: Takeaki Uno
author: Ryuhei Uehara
published in: Journal of Discrete Algorithms
publication date: 2008-08-08T00:00:00Z
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5309336
zbMATH Keywords: chordal graph
zbMATH Keywords: counting
zbMATH Keywords: enumeration
zbMATH Keywords: independent set
zbMATH Keywords: NP-completeness
zbMATH Keywords: \#P-completeness
zbMATH Keywords: polynomial time algorithm
MaRDI profile type: MaRDI publication profile
full work available at URL: j.jda.2006.07.006
OpenAlex ID: W2151864939
cites work: On the Desirability of Acyclic Database Schemes
cites work: Q4288578
cites work: Graph Classes: A Survey
cites work: A characterisation of rigid circuit graphs
cites work: Q4551369
cites work: Generating and characterizing the perfect elimination orderings of a chordal graph
cites work: The weighted independent domination problem is NP-complete for chordal graphs
cites work: All maximal independent sets and dynamic dominance for sparse graphs
cites work: Independent domination in chordal graphs
cites work: A threshold of ln n for approximating set cover
cites work: The Parameterized Complexity of Counting Problems
cites work: Incidence matrices and interval graphs
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: Algorithmic graph theory and perfect graphs
cites work: Efficient Parallel Algorithms for Chordal Graphs
cites work: Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
cites work: Graph-Theoretic Concepts in Computer Science
cites work: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: Efficient graph representations
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 counting in sparse, regular, and planar graphs
DOI: 10.1016/J.JDA.2006.07.006
description: scientific article; zbMATH DE number 5309336