Counting independent sets in tree convex bipartite graphs

DOI10.1016/j.dam.2016.08.017zbMath1352.05146OpenAlexW2558138609MaRDI QIDQ730492

Chien-Min Chen, Min-Sheng Lin

Publication date: 28 December 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2016.08.017

zbMATH Keywords

independent setsmaximal independent setscounting problemtree convex bipartite graphsindependent perfect dominating sets

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (14)

Complexity issues of perfect secure domination in graphs ⋮ Counting independent sets and maximal independent sets in some subclasses of bipartite graphs ⋮ Linear-time algorithms for counting independent sets in bipartite permutation graphs ⋮ Complexity aspects of variants of independent Roman domination in graphs ⋮ Counting independent sets in tricyclic graphs ⋮ Simple linear-time algorithms for counting independent sets in distance-hereditary graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Counting independent sets in cocomparability graphs ⋮ Unnamed Item ⋮ Algorithmic Aspects of Quasi-Total Roman Domination in Graphs ⋮ Complexity of Roman {2}-domination and the double Roman domination in graphs ⋮ Algorithmic aspects of Roman domination in graphs ⋮ Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth

Cites Work

• Feedback vertex sets on restricted bipartite graphs
• Counting independent sets in a tolerance graph
• Fast and simple algorithms to count the number of vertex covers in an interval graph
• Counting the number of independent sets in chordal graphs
• The weighted perfect domination problem and its variants
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Independent Domination on Tree Convex Bipartite Graphs
• Two Hardness Results on Feedback Vertex Sets
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems
• The Complexity of Planar Counting Problems
• Maximum matching in a convex bipartite graph

This page was built for publication: Counting independent sets in tree convex bipartite graphs