Counting independent sets in tree convex bipartite graphs
DOI10.1016/J.DAM.2016.08.017zbMATH Open1352.05146OpenAlexW2558138609MaRDI QIDQ730492FDOQ730492
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
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
independent setscounting problemmaximal independent setstree convex bipartite graphsindependent perfect dominating sets
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)
Cites Work
- 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 counting in sparse, regular, and planar graphs
- Independent domination on tree convex bipartite graphs
- Two Hardness Results on Feedback Vertex Sets
- Feedback vertex sets on restricted bipartite graphs
- Maximum matching in a convex bipartite graph
- The weighted perfect domination problem and its variants
- The Complexity of Planar Counting Problems
- Counting the number of independent sets in chordal graphs
- Counting independent sets in a tolerance graph
- Fast and simple algorithms to count the number of vertex covers in an interval graph
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
- Algorithmic Aspects of Quasi-Total Roman Domination in Graphs
- Title not available (Why is that?)
- Linear-time algorithms for counting independent sets in bipartite permutation graphs
- 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)
