Copertina

Fine-Grained Complexity of Multiple Domination and Dominating Patterns in Sparse Graphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Künnemann, Marvin, Redzic, Mirza
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms F.2
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Engineering Dominating Patterns: A Fine-grained Case Study
di: Dransfeld, Jonathan, et al.
Pubblicazione: (2025)

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

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

What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing
di: Blin, Lélia, et al.
Pubblicazione: (2024)

Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
di: Bojikian, Narek, et al.
Pubblicazione: (2025)

SimdQuickHeap: The QuickHeap Reconsidered
di: Breitling, Johannes, et al.
Pubblicazione: (2026)

Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time $O (m^{1.31})$
di: Spielman, Daniel A., et al.
Pubblicazione: (2003)

On the Parameterized Complexity of Diverse SAT
di: Misra, Neeldhara, et al.
Pubblicazione: (2024)

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

Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
di: Ahn, Jungho, et al.
Pubblicazione: (2025)

A Simple yet Exact Analysis of the MultiQueue
di: Walzer, Stefan, et al.
Pubblicazione: (2024)

On Hardness and Approximation of Broadcasting in Structured Graphs
di: Bringolf, Jeffrey, et al.
Pubblicazione: (2025)

Colorful Vertex Recoloring of Bipartite Graphs
di: Patt-Shamir, Boaz, et al.
Pubblicazione: (2025)

A Linear-Time 1.5-Approximation for Broadcasting in k-Cycle Graphs
di: Bringolf, Jeffrey, et al.
Pubblicazione: (2025)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
di: Saha, Barna, et al.
Pubblicazione: (2024)

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $Δ$-Coloring
di: Assadi, Sepehr, et al.
Pubblicazione: (2022)

Multiplication of 0-1 matrices via clustering
di: Jansson, Jesper, et al.
Pubblicazione: (2025)

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
di: Chuzhoy, Julia, et al.
Pubblicazione: (2025)

Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs
di: Roditty, Liam, et al.
Pubblicazione: (2026)

Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs
di: Mosenzon, Ron
Pubblicazione: (2025)

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

Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures
di: Hommelsheim, Felix, et al.
Pubblicazione: (2025)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
di: DeHaan, Ian, et al.
Pubblicazione: (2024)

Finding All Bounded-Length Simple Cycles in a Directed Graph -- Revisited
di: Bauernöppel, Frank, et al.
Pubblicazione: (2025)

Engineering Compressed Matrix Multiplication with the Fast Walsh-Hadamard Transform
di: Andersson, Joel, et al.
Pubblicazione: (2026)

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

Near-Linear Time Computation of Welzl Orders on Graphs with Linear Neighborhood Complexity
di: Dreier, Jan, et al.
Pubblicazione: (2026)

On the Complexity of Signed Roman Domination
di: Reddy, Sangam Balchandar
Pubblicazione: (2025)

On the I/O Complexity of the CYK Algorithm and of a Family of Related DP Algorithms
di: De Stefani, Lorenzo, et al.
Pubblicazione: (2024)

The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs
di: Chauhan, Archit, et al.
Pubblicazione: (2024)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
di: de Berg, Mark, et al.
Pubblicazione: (2026)

Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
di: Spielman, Daniel A., et al.
Pubblicazione: (2006)

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

Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication
di: Elkin, Michael, et al.
Pubblicazione: (2024)

Fine-Grained Computation in 3-Space: Matrix Multiplication and Graph Problems
di: Stout, Quentin F.
Pubblicazione: (2024)

Complexity of Finding and Enumerating Interconnection Trees
di: Demange, Noé, et al.
Pubblicazione: (2026)

Residue Domination in Bounded-Treewidth Graphs
di: Greilhuber, Jakob, et al.
Pubblicazione: (2024)

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

U-index: A Universal Indexing Framework for Matching Long Patterns
di: Ayad, Lorraine A. K., et al.
Pubblicazione: (2025)