Counting the number of vertex covers in a trapezoid graph

DOI10.1016/J.IPL.2009.08.003MaRDI QIDQ990956zbMATHOpenAlexFDO

Authors Min-Sheng Lin, Yung-Jui Chen

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

vertex covercombinatorial problemscounting problemstrapezoid graph

Mathematics Subject Classification ID

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

Recommendations

• Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph
• Fast and simple algorithms to count the number of vertex covers in an interval graph
• Efficient algorithm for the vertex connectivity of trapezoid graphs
• Counting independent sets in tricyclic graphs
• Trapezoid graphs and generalizations, geometry and algorithms

Cites work

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

Cited in

(9)

• The hub number of co-comparability graphs
• Counting maximal independent sets in directed path graphs
• Efficient algorithm for the vertex connectivity of trapezoid graphs
• Fast and simple algorithms to count the number of vertex covers in an interval graph
• Closest pair and the post office problem for stochastic points
• 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
• Efficient maximum matching algorithms for trapezoid graphs
• Counting independent sets in a tolerance graph

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

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