Hypergraph dualization with \textsf{FPT}-delay parameterized by the degeneracy and dimension

DOI10.1007/978-3-031-63021-7_9MaRDI QIDQ7021103zbMATH OpenFDO

Authors Valentin Bartier, Oscar Defrain, Fionn Mc Inerney

Publication date 28 February 2025

Full work available at URL https://doi.org/10.1007/978-3-031-63021-7_9

zbMATH Keywords

\textsf{FPT}-delay enumerationalgorithmic enumerationhypergraph dualizationminimal dominating setsminimal transversals

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• A New Algorithm for Generating All the Maximal Independent Sets
• A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs
• Adapted List Coloring of Graphs and Hypergraphs
• Bounding the trace function of a hypergraph with applications
• Computational aspects of monotone dualization: a brief survey
• Efficient enumeration of induced subtrees in a K-degenerate graph
• Enumerating minimal dominating sets in \(K_t\)-free graphs and variants
• Enumerating minimal dominating sets in chordal bipartite graphs
• Enumerating Minimal Dominating Sets in Triangle-Free Graphs
• Enumeration complexity
• Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties
• Geometric amortization of enumeration algorithms
• scientific article; zbMATH DE number 6519673 (Why is no real title available?)
• scientific article; zbMATH DE number 1354130 (Why is no real title available?)
• scientific article; zbMATH DE number 2090012 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Maximal irredundant set enumeration in bounded-degeneracy and bounded-degree hypergraphs
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• New results on monotone dualization and generating hypergraph transversals
• On generating all maximal independent sets
• On subgraphs of bounded degeneracy in hypergraphs
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs
• On the enumeration of minimal dominating sets and related notions
• Online conflict-free colouring for hypergraphs
• Output-polynomial enumeration on graphs of bounded (local) linear MIM-width
• Paradigms for parameterized enumeration
• Parameterized algorithms
• Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
• Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
• Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
• Smallest-last ordering and clustering and graph coloring algorithms
• Some Fixed-Parameter Tractable Classes of Hypergraph Duality and Related Problems
• Sparsity. Graphs, structures, and algorithms

Cited in

(3)

• Enumerating minimal dominating sets and variants in chordal bipartite graphs
• On the enumeration of signatures of XOR-CNF's
• Enumeration kernels for vertex cover and feedback vertex set

This page was built for publication: Hypergraph dualization with \textsf{FPT}-delay parameterized by the degeneracy and dimension

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