Enumeration and maximum number of minimal connected vertex covers in graphs

DOI10.1016/j.ejc.2017.07.015zbMath1373.05008OpenAlexW2964087509MaRDI QIDQ1678095

Pinar Heggernes, Petr A. Golovach, 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

distance-hereditary graphschordal graphs

Mathematics Subject Classification ID

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

Related Items (7)

On the number of connected sets in bounded degree graphs ⋮ Maximal and maximum dissociation sets in general and triangle-free graphs ⋮ Enumeration of minimal connected dominating sets for chordal graphs ⋮ Minimum number of maximal dissociation sets in trees ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ Enumeration and maximum number of maximal irredundant sets for chordal graphs ⋮ Extension and its price for the connected vertex cover problem

Cites Work

• Unnamed Item
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• Enumerating minimal subset feedback vertex sets
• Exact exponential algorithms.
• Enumerating maximal independent sets with applications to graph colouring.
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Distance-hereditary graphs
• On generating all maximal independent sets
• A note on the complexity of the chromatic number problem
• Algorithmic graph theory and perfect graphs
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Subset feedback vertex sets in chordal graphs
• Exact algorithms for graph homomorphisms
• Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs
• Deterministic Parameterized Connected Vertex Cover
• Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs
• Finding Induced Subgraphs via Minimal Triangulations
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• A New Algorithm for Generating All the Maximal Independent Sets
• Graph Classes: A Survey
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• Feedback Vertex Sets in Tournaments
• Maximal Induced Matchings in Triangle-Free Graphs
• Algorithms and Computation
• On cliques in graphs

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