Enumeration and maximum number of minimal connected vertex covers in graphs

DOI10.1016/J.EJC.2017.07.015MaRDI QIDQ1678095zbMATH OpenOpenAlexFDO

Authors Petr A. Golovach, Pinar Heggernes, Dieter Kratsch

Publication date 14 November 2017

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2017.07.015

zbMATH Keywords

chordal graphsdistance-hereditary graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Exact enumeration problems, generating functions (05A15) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs
• Complexity and Approximation Results for the Connected Vertex Cover Problem
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Enumeration of minimal connected dominating sets for chordal graphs
• Enumerating minimal connected dominating sets in graphs of bounded chordality

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• A note on the complexity of the chromatic number problem
• Algorithmic graph theory and perfect graphs
• Algorithms and Computation
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Deterministic parameterized connected vertex cover
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Distance-hereditary graphs
• Enumerating maximal independent sets with applications to graph colouring.
• Enumerating minimal subset feedback vertex sets
• Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs
• Exact algorithms for graph homomorphisms
• Exact exponential algorithms.
• Feedback vertex sets in tournaments
• Finding induced subgraphs via minimal triangulations
• Graph Classes: A Survey
• Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• On cliques in graphs
• On generating all maximal independent sets
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Subset feedback vertex sets in chordal graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs

Cited in

(12)

• Enumeration of connected graph coverings
• Extension and its price for the connected vertex cover problem
• Maximal and maximum dissociation sets in general and triangle-free graphs
• Enumeration and maximum number of maximal irredundant sets for chordal graphs
• Minimum number of maximal dissociation sets in trees
• Enumeration of minimal connected dominating sets for chordal graphs
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• On the number of connected sets in bounded degree graphs
• Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs
• Minimal vertex covers in infinite hypergraphs
• The Alcuin Number of a Graph and Its Connections to the Vertex Cover Number
• scientific article; zbMATH DE number 3910427 (Why is no real title available?)

This page was built for publication: Enumeration and maximum number of minimal connected vertex covers in graphs

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