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 setvertex coverinterval graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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)

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)

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