Counting the number of vertex covers in a trapezoid graph
DOI10.1016/J.IPL.2009.08.003zbMATH Open1197.05073OpenAlexW2076516201MaRDI QIDQ990956FDOQ990956
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
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
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)
Cites Work
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- On efficient fixed-parameter algorithms for weighted vertex cover
- An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs
- Optimal sequential and parallel algorithms to compute all cut vertices on trapezoid graphs
- Chaining algorithms for multiple genome comparison
- Efficient algorithms for the minimum connected domination on trapezoid graphs
- Counting the number of independent sets in chordal graphs
- Fast and simple algorithms to count the number of vertex covers in an interval graph
- A note on the size of minimal covers
- Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph
Cited In (9)
- Efficient algorithm for the vertex connectivity of trapezoid graphs
- Linear time algorithms for counting the number of minimal vertex covers with minimum/maximum size in an interval graph
- The hub number of co-comparability graphs
- Counting independent sets in a tolerance graph
- Fast and simple algorithms to count the number of vertex covers in an interval graph
- Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
- Counting maximal independent sets in directed path graphs
- Efficient maximum matching algorithms for trapezoid graphs
- Closest pair and the post office problem for stochastic points
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)
