Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph
From MaRDI portal
Publication:963461
DOI10.1016/j.ipl.2008.03.008zbMath1185.05138OpenAlexW1981341188MaRDI QIDQ963461
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
algorithmscombinatorial problemsinterval graphscounting problemsmaximum minimal vertex coversminimum vertex covers
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
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