Counting independent sets and maximal independent sets in some subclasses of bipartite graphs

DOI10.1016/J.DAM.2018.05.045zbMath1401.05149OpenAlexW2809443908WikidataQ129651044 ScholiaQ129651044MaRDI QIDQ1627864

Min-Sheng Lin

Publication date: 3 December 2018

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

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

zbMATH Keywords

independent setsmaximal independent setscounting problemtree convex bipartiteconvex bipartitepath-tree bipartite

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Counting dominating sets in some subclasses of bipartite graphs ⋮ Counting independent sets in cocomparability graphs

Cites Work

• Unnamed Item
• Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
• Feedback vertex sets on restricted bipartite graphs
• Counting independent sets in a tolerance graph
• Counting independent sets in tree convex bipartite graphs
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• 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

This page was built for publication: Counting independent sets and maximal independent sets in some subclasses of bipartite graphs