Locally definable vertex set properties are efficiently enumerable

DOI10.1016/J.DAM.2020.05.037MaRDI QIDQ1983133zbMATH OpenOpenAlexFDO

Authors Sarah Blind, Nadia Creignou, Frédéric Olive

Publication date 15 September 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2020.05.037

zbMATH Keywords

complexityenumerationvertex set properties

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Recommendations

• On the enumeration and counting of minimal dominating sets in interval and permutation graphs
• Enumeration of minimal dominating sets and variants
• Enumeration of minimal connected dominating sets for chordal graphs
• Efficient enumeration of dominating sets for sparse 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?)
• Combinatorial bounds via measure and conquer
• Enumerating minimal connected dominating sets in graphs of bounded chordality
• Enumerating minimal dominating sets in \(K_t\)-free graphs and variants
• Enumeration of maximal irredundant sets for claw-free graphs
• Graph theory
• Interval graphs and related topics
• Minimal dominating sets in graph classes: combinatorial bounds and enumeration
• On the enumeration and counting of minimal dominating sets in interval and permutation graphs
• On the enumeration of minimal dominating sets and related notions
• On the number of minimal dominating sets on some graph classes
• The Private Neighbor Cube
• Treewidth and Pathwidth of Permutation Graphs

This page was built for publication: Locally definable vertex set properties are efficiently enumerable

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