Fast and simple algorithms to count the number of vertex covers in an interval graph

DOI10.1016/j.ipl.2006.12.002zbMath1185.05137OpenAlexW2090804980MaRDI QIDQ845989

Min-Sheng Lin

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.12.002

zbMATH Keywords

algorithmscountingindependent setinterval graphvertex cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Linear-time algorithms for counting independent sets in bipartite permutation graphs ⋮ The \(p\)-Maxian problem on interval graphs ⋮ Counting independent sets in tricyclic graphs ⋮ Simple linear-time algorithms for counting independent sets in distance-hereditary graphs ⋮ Counting independent sets in a tolerance graph ⋮ Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph ⋮ Counting maximal independent sets in directed path graphs ⋮ Counting the number of vertex covers in a trapezoid graph ⋮ Counting independent sets in tree convex bipartite graphs

Cites Work

• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Fast and simple algorithms to count the number of vertex covers in an interval graph