Buchumschlag

Hardness and Algorithmic Results for Roman \{3\}-Domination

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Reddy, Sangam Balchandar
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity 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

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

On the complexity of global Roman domination problem in graphs
von: Reddy, Sangam Balchandar, et al.
Veröffentlicht: (2026)

Algorithms for Minimum Membership Dominating Set Problem
von: Reddy, Sangam Balchandar, et al.
Veröffentlicht: (2024)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
von: Guruswami, Venkatesan, 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)

Hardness Results on Characteristics for Elastic-Degenerated Strings
von: Köppl, Dominik, et al.
Veröffentlicht: (2024)

Algorithms and Hardness for Estimating Statistical Similarity
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2025)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
von: Gadekar, Ameet, et al.
Veröffentlicht: (2025)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2026)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2025)

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

Dominating Set Knapsack: Profit Optimization on Dominating Sets
von: Singh, Sipra
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)

Fine-Grained Classification Of Detecting Dominating Patterns
von: Dransfeld, Jonathan, et al.
Veröffentlicht: (2025)

Hardness of Dynamic Core and Truss Decompositions
von: Couto, Yan S., et al.
Veröffentlicht: (2025)

Sampling Permutations with Cell Probes is Hard
von: Alekseev, Yaroslav, et al.
Veröffentlicht: (2025)

Improved Hardness-of-Approximation for Token Swapping
von: Hiken, Sam, et al.
Veröffentlicht: (2024)

k-SUM Hardness Implies Treewidth-SETH
von: Lampis, Michael
Veröffentlicht: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
von: Kleinberg, Robert, et al.
Veröffentlicht: (2026)

Sumplete is Hard, Even with Two Different Numbers
von: Ruangwises, Suthee
Veröffentlicht: (2023)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2026)

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

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
von: Curticapean, Radu, et al.
Veröffentlicht: (2024)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
von: Esmer, Barış Can, et al.
Veröffentlicht: (2024)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
von: Adriaens, Florian, et al.
Veröffentlicht: (2024)

Refining the Complexity Landscape of Speed Scaling: Hardness and Algorithms
von: Antoniadis, Antonios, et al.
Veröffentlicht: (2025)

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

Testing Sumsets is Hard
von: Chen, Xi, 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)

Novel Complexity Results for Temporal Separators with Deadlines
von: Dondi, Riccardo, et al.
Veröffentlicht: (2025)

On the Parameterized Complexity of Odd Coloring
von: Bhyravarapu, Sriram, et al.
Veröffentlicht: (2025)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2026)

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

Deciding if a DAG is Interesting is Hard
von: De Carufel, Jean-Lou, et al.
Veröffentlicht: (2025)

Efficient Catalytic Graph Algorithms
von: Cook, James, et al.
Veröffentlicht: (2025)

Improved Algorithm for Permutation Testing
von: Zhang, Xiaojin
Veröffentlicht: (2020)

Pseudodeterministic Algorithms for Minimum Cut Problems
von: Agarwala, Aryan, et al.
Veröffentlicht: (2025)

Sensitivity Lower Bounds for Approximaiton Algorithms
von: Fleming, Noah, et al.
Veröffentlicht: (2024)

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