Buchumschlag

Fine-Grained Classification Of Detecting Dominating Patterns

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Dransfeld, Jonathan, Künnemann, Marvin, Redzic, Mirza
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Engineering Dominating Patterns: A Fine-grained Case Study
von: Dransfeld, Jonathan, et al.
Veröffentlicht: (2025)

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

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

Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
von: Dudek, Bartłomiej, et al.
Veröffentlicht: (2026)

The Fine-Grained Complexity of Episode Matching
von: Bille, Philip, et al.
Veröffentlicht: (2021)

The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
von: Bringmann, Karl, et al.
Veröffentlicht: (2023)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
von: Rohwedder, Lars, et al.
Veröffentlicht: (2024)

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

On the Complexity of Signed Roman Domination
von: Reddy, Sangam Balchandar
Veröffentlicht: (2025)

Residue Domination in Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2024)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Hardness and Algorithmic Results for Roman \{3\}-Domination
von: Reddy, Sangam Balchandar
Veröffentlicht: (2025)

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

Fine-Grained Complexity of Continuous Euclidean k-Center
von: Blank, Lotte, 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)

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

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
von: Focke, Jacob, et al.
Veröffentlicht: (2022)

On $[1,2]$-Domination in Interval and Circle Graphs
von: Meybodi, Mohsen Alambardar, et al.
Veröffentlicht: (2024)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
von: Nederlof, Jesper
Veröffentlicht: (2026)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
von: Focke, Jacob, et al.
Veröffentlicht: (2023)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
von: Mu, Ta-Yu, et al.
Veröffentlicht: (2024)

A Note on Fine-Grained Quantum Reductions for Linear Algebraic Problems
von: Doney, Kyle, et al.
Veröffentlicht: (2025)

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
von: Huang, Jeremy Ahrens, et al.
Veröffentlicht: (2024)

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
von: Chia, Nai-Hui, et al.
Veröffentlicht: (2026)

Detecting Low-Degree Truncation
von: De, Anindya, et al.
Veröffentlicht: (2024)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
von: Garg, Sumegha, et al.
Veröffentlicht: (2026)

Distance Vector Domination
von: Cordasco, Gennaro, et al.
Veröffentlicht: (2024)

The Fine-Grained Complexity of Gradient Computation for Training Large Language Models
von: Alman, Josh, et al.
Veröffentlicht: (2024)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
von: Chakraborty, Dipayan, et al.
Veröffentlicht: (2024)

Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition
von: Leake, Jonathan, et al.
Veröffentlicht: (2025)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
von: Leake, Jonathan, et al.
Veröffentlicht: (2025)

On Detecting $H$-Induced Minors for Small $H$
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2026)

(Independent) Roman Domination Parameterized by Distance to Cluster
von: Ashok, Pradeesha, et al.
Veröffentlicht: (2024)

The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
von: Fischer, Nick, et al.
Veröffentlicht: (2025)

On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems
von: Scheffler, Robert
Veröffentlicht: (2025)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
von: Abboud, Amir, et al.
Veröffentlicht: (2026)

Parameterized Complexity of (d,r)-Domination via Modular Decomposition
von: Cordasco, Gennaro, et al.
Veröffentlicht: (2024)

The Trichotomy of Regular Property Testing
von: Bathie, Gabriel, et al.
Veröffentlicht: (2025)

Downward self-reducibility in the total function polynomial hierarchy
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
von: Fujie, Yuto, et al.
Veröffentlicht: (2025)