Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph

DOI10.1016/j.ipl.2008.03.008zbMath1185.05138OpenAlexW1981341188MaRDI QIDQ963461

Yung-Jui Chen, Min-Sheng Lin

Publication date: 19 April 2010

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

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

zbMATH Keywords

algorithmscombinatorial problemsinterval graphscounting problemsmaximum minimal vertex coversminimum vertex covers

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) 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

Counting the number of vertex covers in a trapezoid graph

Cites Work

• Fast and simple algorithms to count the number of vertex covers in an interval graph
• A unified approach to domination problems on interval graphs
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Enumeration and Reliability Problems
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Graph-Theoretic Concepts in Computer Science