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

DOI10.1016/J.IPL.2006.12.002MaRDI QIDQ845989zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph
• Counting the number of vertex covers in a trapezoid graph
• Generalized vertex covering in interval graphs
• On counting interval lengths of interval graphs
• scientific article; zbMATH DE number 4049085

Cites work

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

Cited in

(9)

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

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

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