Cover Image

Engineering Dominating Patterns: A Fine-grained Case Study

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dransfeld, Jonathan, Künnemann, Marvin, Redzic, Mirza, Wunderlich, Marcus
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fine-Grained Classification Of Detecting Dominating Patterns
by: Dransfeld, Jonathan, et al.
Published: (2025)

Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs
by: Künnemann, Marvin, et al.
Published: (2024)

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

Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
by: Dudek, Bartłomiej, et al.
Published: (2026)

A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
by: Bringmann, Karl, et al.
Published: (2024)

The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
by: Bringmann, Karl, et al.
Published: (2023)

Confluence of the Node-Domination and Edge-Domination Hypergraph Rewrite Rules
by: Amarilli, Antoine, et al.
Published: (2025)

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
by: Fischer, Nick, et al.
Published: (2024)

Exact Optimization for Minimum Dominating Sets
by: Zhu, Enqiang, et al.
Published: (2025)

Dominating Set with Quotas: Balancing Coverage and Constraints
by: Chatterjee, Sobyasachi, et al.
Published: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
by: Nederlof, Jesper
Published: (2026)

Revisiting a Successful Reduction Rule for Dominating Set
by: Geis, Lukas, et al.
Published: (2025)

Non-Signaling Locality Lower Bounds for Dominating Set
by: Fleming, Noah, et al.
Published: (2026)

Structural Parameterization of Locating-Dominating Set and Test Cover
by: Chakraborty, Dipayan, et al.
Published: (2024)

Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets
by: Karathanasis, Konstantinos, et al.
Published: (2025)

Approximations for Fault-Tolerant Total and Partial Positive Influence Domination
by: Lamprou, Ioannis, et al.
Published: (2025)

On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
by: Kwok, Tsz Chiu, et al.
Published: (2025)

An $O(n^5)$-Time Algorithm for Optimal Broadcast Domination
by: Papadopoulos, Kleitos
Published: (2026)

Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
by: Goyal, Dishant, et al.
Published: (2024)

Constant matters: Fine-grained Complexity of Differentially Private Continual Observation
by: Fichtenberger, Hendrik, et al.
Published: (2022)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
by: Saito, Rin, et al.
Published: (2025)

Resilient Pattern Mining
by: Bian, Pengxin, et al.
Published: (2025)

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

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

Dominating Set Knapsack: Profit Optimization on Dominating Sets
by: Singh, Sipra
Published: (2025)

Quantum Pattern Matching with Wildcards
by: Seddighin, Masoud, et al.
Published: (2025)

Pattern Matching with Mismatches and Wildcards
by: Bathie, Gabriel, et al.
Published: (2024)

Inapproximability of Counting Permutation Patterns
by: Opler, Michal
Published: (2026)

Pattern Discovery in Colored Strings
by: Lipták, Zsuzsanna, et al.
Published: (2020)

Approximate Circular Pattern Matching
by: Charalampopoulos, Panagiotis, et al.
Published: (2022)

Dynamic Pattern Matching with Wildcards
by: Naeini, Arshia Ataee, et al.
Published: (2026)

Enhanced Graph Pattern Matching
by: Cotumaccio, Nicola
Published: (2024)

Pattern Masking for Dictionary Matching
by: Charalampopoulos, Panagiotis, et al.
Published: (2020)

String Indexing with Compressed Patterns
by: Bille, Philip, et al.
Published: (2019)

Connected Partitions via Connected Dominating Sets
by: Niklanovits, Aikaterini, et al.
Published: (2025)

Fast Pattern Matching with Epsilon Transitions
by: Cotumaccio, Nicola
Published: (2025)

Better Indexing for Rectangular Pattern Matching
by: Gawrychowski, Paweł, et al.
Published: (2025)

Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)

On Fine-Grained Distinct Element Estimation
by: Diakonikolas, Ilias, et al.
Published: (2025)

Near-Optimal Property Testers for Pattern Matching
by: Jin, Ce, et al.
Published: (2025)