Buchumschlag

Revisiting a Successful Reduction Rule for Dominating Set

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Geis, Lukas, Leonhardt, Alexander, Meintrup, Johannes, Meyer, Ulrich, Penschuck, Manuel, Retschmeier, Lukas
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Uniform Sampling of Negative Edge Weights in Shortest Path Networks
von: Geis, Lukas, et al.
Veröffentlicht: (2024)

Insights into $(k,ρ)$-shortcutting algorithms
von: Leonhardt, Alexander, et al.
Veröffentlicht: (2024)

Succinct Planar Encoding with Minor Operations
von: Kammer, Frank, et al.
Veröffentlicht: (2023)

Faster Private Minimum Spanning Trees
von: Pagh, Rasmus, et al.
Veröffentlicht: (2024)

Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings
von: Elberfeld, Michael, et al.
Veröffentlicht: (2025)

Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings
von: Hammer, Nina, et al.
Veröffentlicht: (2022)

The Correlated Gaussian Sparse Histogram Mechanism
von: Lebeda, Christian Janos, et al.
Veröffentlicht: (2024)

Private Lossless Multiple Release
von: Andersson, Joel Daniel, et al.
Veröffentlicht: (2025)

Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation
von: Pagh, Rasmus, et al.
Veröffentlicht: (2024)

Sorting and Ranking of Self-Delimiting Numbers with Applications to Outerplanar Graph Isomorphism
von: Kammer, Frank, et al.
Veröffentlicht: (2020)

Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous
von: Dogeas, Konstantinos, et al.
Veröffentlicht: (2023)

Confluence of the Node-Domination and Edge-Domination Hypergraph Rewrite Rules
von: Amarilli, Antoine, et al.
Veröffentlicht: (2025)

A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
von: Großmann, Ernestine, et al.
Veröffentlicht: (2024)

Exact Optimization for Minimum Dominating Sets
von: Zhu, Enqiang, et al.
Veröffentlicht: (2025)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
von: Saito, Rin, et al.
Veröffentlicht: (2025)

Dominating Set with Quotas: Balancing Coverage and Constraints
von: Chatterjee, Sobyasachi, et al.
Veröffentlicht: (2026)

Dominating Set Knapsack: Profit Optimization on Dominating Sets
von: Singh, Sipra
Veröffentlicht: (2025)

Non-Signaling Locality Lower Bounds for Dominating Set
von: Fleming, Noah, et al.
Veröffentlicht: (2026)

Structural Parameterization of Locating-Dominating Set and Test Cover
von: Chakraborty, Dipayan, et al.
Veröffentlicht: (2024)

Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets
von: Karathanasis, Konstantinos, et al.
Veröffentlicht: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
von: Solomon, Shay, et al.
Veröffentlicht: (2023)

RLZ-r and LZ-End-r: Enhancing Move-r
von: Dinklage, Patrick, et al.
Veröffentlicht: (2025)

Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
von: Goyal, Dishant, et al.
Veröffentlicht: (2024)

Connected Partitions via Connected Dominating Sets
von: Niklanovits, Aikaterini, et al.
Veröffentlicht: (2025)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
von: de Berg, Mark, et al.
Veröffentlicht: (2026)

An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
von: Kurita, Kazuhiro, et al.
Veröffentlicht: (2022)

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
von: Großmann, Ernestine, et al.
Veröffentlicht: (2026)

Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
von: Fischer, Nick, et al.
Veröffentlicht: (2026)

Search-Space Reduction Via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion
von: Jansen, Bart M. P., et al.
Veröffentlicht: (2024)

Analysis of a Random Local Search Algorithm for Dominating Set
von: Higl, Hendrik
Veröffentlicht: (2026)

Stable Approximation Algorithms for Dominating Set and Independent Set
von: de Berg, Mark, et al.
Veröffentlicht: (2024)

Computing Dominating Sets in Disk Graphs with Centers in Convex Position
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2026)

Lower bounds for graph reconstruction with maximal independent set queries
von: Michel, Lukas, et al.
Veröffentlicht: (2024)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
von: Chu, Huairui, et al.
Veröffentlicht: (2023)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
von: Herrmann, Anton, et al.
Veröffentlicht: (2025)

Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
von: Biedl, Therese, et al.
Veröffentlicht: (2026)

FPT Approximations for Fair $k$-Min-Sum-Radii
von: Carta, Lena, et al.
Veröffentlicht: (2024)

The Trie Measure, Revisited
von: Alanko, Jarno N., et al.
Veröffentlicht: (2025)

Wavelet Forests Revisited
von: Chiu, Eric, et al.
Veröffentlicht: (2026)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2025)