Cover Image

On the complexity of Multipacking

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Das, Sandip, Islam, Sk Samim, Lokshtanov, Daniel
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Multipacking and broadcast domination on cactus graph and its impact on hyperbolic graph
by: Das, Sandip, et al.
Published: (2023)

Multipacking in Euclidean Metric Space
by: Das, Arun Kumar, et al.
Published: (2024)

Multipacking on graphs and Euclidean metric space
by: Islam, Sk Samim
Published: (2026)

Parameterized complexity of $r$-Hop, $r$-Step, and $r$-Hop Roman Domination
by: Das, Sandip, et al.
Published: (2026)

On the Complexity of Hop Domination and 2-Step Domination in Graph Classes
by: Das, Sandip, et al.
Published: (2026)

Between the deterministic and non-deterministic query complexity
by: Gerbner, Dániel
Published: (2019)

Proof complexity of positive branching programs
by: Das, Anupam, et al.
Published: (2021)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
by: Lokshtanov, Daniel, et al.
Published: (2024)

Breaking the Temporal Complexity Barrier: Bucket Calculus for Parallel Machine Scheduling
by: Mohammad, Noor Islam S.
Published: (2026)

The complexity of computing in continuous time: space complexity is precision
by: Blanc, Manon, et al.
Published: (2024)

Query complexity of Boolean functions on the middle slice of the cube
by: Gerbner, Dániel, et al.
Published: (2023)

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

Unambiguous parity-query complexity
by: Gavinsky, Dmytro
Published: (2024)

FeatPCA: A feature subspace based principal component analysis technique for enhancing clustering of single-cell RNA-seq data
by: Islam, Md Romizul, et al.
Published: (2025)

Computational complexity of isometric tensor network states
by: Malz, Daniel, et al.
Published: (2024)

On complexity of restricted fragments of Decision DNNF
by: Calí, Andrea, et al.
Published: (2025)

Relation between broadcast domination and multipacking numbers on chordal and other hyperbolic graphs
by: Das, Sandip, et al.
Published: (2023)

Unconventional complexity classes in unconventional computing (extended abstract)
by: Porreca, Antonio E.
Published: (2024)

The complexity of convexity number and percolation time in the cycle convexity
by: Lima, Carlos V. G. C., et al.
Published: (2024)

Some structural complexity results for $\exists\mathbb R$
by: Meer, Klaus, et al.
Published: (2025)

Inapproximability of the independent set polynomial in the complex plane
by: Bezakova, Ivona, et al.
Published: (2017)

A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
by: Folea, Rares, et al.
Published: (2025)

A primer on the closure of algebraic complexity classes under factoring
by: Bhargav, C. S., et al.
Published: (2025)

Communication complexity of pointer chasing via the fixed-set lemma
by: Viola, Emanuele
Published: (2025)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
by: Cai, Jin-Yi, et al.
Published: (2024)

On the complexity of embedding in graph products
by: Biedl, Therese, et al.
Published: (2023)

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
by: Bender, Matías, et al.
Published: (2025)

On one-way functions and the average time complexity of almost-optimal compression
by: Zimand, Marius
Published: (2024)

Average-case deterministic query complexity of boolean functions with fixed weight
by: Li, Yuan, et al.
Published: (2024)

On the complexity of global Roman domination problem in graphs
by: Reddy, Sangam Balchandar, et al.
Published: (2026)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
by: Colli, Giordano
Published: (2025)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
by: Goubault-Larrecq, Aliénor, et al.
Published: (2025)

Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes
by: O'Donnell, Ryan, et al.
Published: (2025)

On the complexity of covering points by guillotine cuts
by: Garijo, Delia, et al.
Published: (2026)

Proof complexity of Mal'tsev CSP
by: Gaysin, Azza
Published: (2025)

Encoding of algebraic geometry codes with quasi-linear complexity $O(N\log N)$
by: Li, Songsong, et al.
Published: (2024)

Relations between monotone complexity measures based on decision tree complexity
by: Byramji, Farzan, et al.
Published: (2024)

Hunting a rabbit: complexity, approximability and some characterizations
by: Ben-Ameur, Walid, et al.
Published: (2025)

On $NP \cap coNP$ proof complexity generators
by: Krajicek, Jan
Published: (2025)

Analogy between List Coloring Problems and the Interval $k$-$(γ,μ)$-choosability property: theoretical aspects of complexity
by: Gama, Simone Ingrid Monteiro, et al.
Published: (2025)