Counting independent sets in tree convex bipartite graphs

DOI10.1016/J.DAM.2016.08.017MaRDI QIDQ730492zbMATH OpenOpenAlexFDO

Authors Min-Sheng Lin, Chien-Min Chen

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 setscounting problemmaximal independent setstree convex bipartite graphsindependent perfect dominating sets

Mathematics Subject Classification ID

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

Recommendations

• Counting independent sets and maximal independent sets in some subclasses of bipartite graphs
• Independent domination on tree convex bipartite graphs
• Tree Convex Bipartite Graphs: $\mathcal{NP}$ -Complete Domination, Hamiltonicity and Treewidth
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• Maximum Edge Bicliques in Tree Convex Bipartite Graphs

Cites work

• Counting independent sets in a tolerance graph
• Counting the number of independent sets in chordal graphs
• Fast and simple algorithms to count the number of vertex covers in an interval graph
• Feedback vertex sets on restricted bipartite graphs
• Independent domination on tree convex bipartite graphs
• Maximum matching in a convex bipartite graph
• 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
• The complexity of counting in sparse, regular, and planar graphs
• The weighted perfect domination problem and its variants
• Two Hardness Results on Feedback Vertex Sets

Cited in

(18)

• Complexity issues of perfect secure domination in graphs
• Complexity issues of perfect Roman domination in graphs
• Counting independent sets and maximal independent sets in some subclasses of bipartite graphs
• Complexity of Roman \(\{ 2 \} \)-domination and the double Roman domination in graphs
• Algorithmic aspects of Roman domination in graphs
• Counting independent sets in graphs with bounded bipartite pathwidth
• Algorithmic complexity of triple Roman dominating functions on graphs
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• Total 2-rainbow domination in graphs: complexity and algorithms
• Complexity aspects of variants of independent Roman domination in graphs
• Linear-time algorithms for counting independent sets in bipartite permutation graphs
• Algorithmic Aspects of Quasi-Total Roman Domination in Graphs
• scientific article; zbMATH DE number 7693181 (Why is no real title available?)
• Independent domination on tree convex bipartite graphs
• Counting independent sets in tricyclic graphs
• Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
• Counting independent sets in cocomparability graphs
• Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730492)