Counting the number of vertex covers in a trapezoid graph

DOI10.1016/j.ipl.2009.08.003zbMath1197.05073OpenAlexW2076516201MaRDI QIDQ990956

Yung-Jui Chen, Min-Sheng Lin

Publication date: 1 September 2010

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

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

zbMATH Keywords

combinatorial problemstrapezoid graphvertex covercounting problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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 (7)

Closest pair and the post office problem for stochastic points ⋮ Efficient algorithm for the vertex connectivity of trapezoid graphs ⋮ Simple linear-time algorithms for counting independent sets in distance-hereditary graphs ⋮ Counting independent sets in a tolerance graph ⋮ Counting maximal independent sets in directed path graphs ⋮ The hub number of co-comparability graphs ⋮ Efficient maximum matching algorithms for trapezoid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A note on the size of minimal covers
• Fast and simple algorithms to count the number of vertex covers in an interval graph
• Efficient algorithms for the minimum connected domination on trapezoid graphs
• Counting the number of independent sets in chordal graphs
• Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph
• Trapezoid graphs and their coloring
• Optimal sequential and parallel algorithms to compute all cut vertices on trapezoid graphs
• Chaining algorithms for multiple genome comparison
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs
• The Complexity of Enumeration and Reliability Problems
• On efficient fixed-parameter algorithms for weighted vertex cover

This page was built for publication: Counting the number of vertex covers in a trapezoid graph