Counting independent sets in a tolerance graph

DOI10.1016/j.dam.2014.09.011zbMath1304.05106OpenAlexW1985963532MaRDI QIDQ479039

Min-Sheng Lin, Sheng-Huang Su

Publication date: 5 December 2014

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

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

zbMATH Keywords

tolerance graphsindependent setsmaximal independent setscounting problemindependent perfect dominating sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Counting independent sets and maximal independent sets in some subclasses of bipartite graphs ⋮ Linear-time algorithms for counting independent sets in bipartite permutation graphs ⋮ Simple linear-time algorithms for counting independent sets in distance-hereditary graphs ⋮ Counting independent sets in tree convex bipartite graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Fast and simple algorithms to count the number of vertex covers in an interval graph
• Counting the number of independent sets in chordal graphs
• Counting the number of vertex covers in a trapezoid graph
• Intersection graphs of paths in a tree
• Proper and unit tolerance graphs
• Weighted independent perfect domination on cocomparability graphs
• Counting maximal independent sets in directed path graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• A New Intersection Model and Improved Algorithms for Tolerance Graphs
• The Complexity of Enumeration and Reliability Problems

This page was built for publication: Counting independent sets in a tolerance graph