Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
type: Item
instance of: scholarly article
title: Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
zbMATH Open document ID: 1382.05034
author: Min-Sheng Lin
published in: Discrete Applied Mathematics
publication date: 2018-03-21T00:00:00Z
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6851665
zbMATH Keywords: distance-hereditary graphs
zbMATH Keywords: counting problem
zbMATH Keywords: independent sets
zbMATH Keywords: independent dominating sets
zbMATH Keywords: independent perfect dominating sets
zbMATH Keywords: linear-time algorithms
MaRDI profile type: Publication
full work available at URL: j.dam.2017.12.023
OpenAlex ID: W2783719167
cites work: Distance-hereditary graphs
cites work: A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
cites work: A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
cites work: Domination in distance-hereditary graphs
cites work: Computing maximum stable sets for distance-hereditary graphs
cites work: A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
cites work: Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
cites work: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
cites work: Completely separable graphs
cites work: A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
cites work: Fast and simple algorithms to count the number of vertex covers in an interval graph
cites work: Counting the number of vertex covers in a trapezoid graph
cites work: Counting independent sets in tree convex bipartite graphs
cites work: Counting maximal independent sets in directed path graphs
cites work: Counting independent sets in a tolerance graph
cites work: Weighted efficient domination problem on some perfect graphs
cites work: Counting the number of independent sets in chordal graphs
cites work: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
cites work: The Complexity of Enumeration and Reliability Problems
DOI: 10.1016/J.DAM.2017.12.023
description: scientific article; zbMATH DE number 6851665