Cover Image

Broadcast Graph Is NP-complete

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Xu, Jinghan, Li, Zhiyuan
Format:	Preprint
Published:	2024
Subjects:	Discrete Mathematics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Weighted Treedepth is NP-complete on Graphs of Bounded Degree
by: Dirks, Jona, et al.
Published: (2025)

Efficient $k$-limited Dominating Broadcasts in Product Graphs
by: Bharadwaj, et al.
Published: (2025)

Broadcast via Mobile Agents in a Dynamic Network: Interplay of Graph Properties & Agents
by: Moses Jr., William K., et al.
Published: (2025)

Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete
by: la Tour, Max Dupré, et al.
Published: (2025)

Why Districting Becomes NP-hard
by: Jost, Niklas, et al.
Published: (2025)

On the Extension Theorem for Packing Steiner Forests
by: Zeng, Jinghan A
Published: (2026)

Determining the Outerthickness of Graphs Is NP-Hard
by: Lee, Pin-Hsian, et al.
Published: (2026)

Slant/Gokigen Naname is NP-complete, and Some Variations are in P
by: Lynch, Jayson, et al.
Published: (2025)

p-complete square-free Word-representation of Word-representable Graphs
by: Das, Biswajit, et al.
Published: (2025)

Source-Oblivious Broadcast
by: Fraigniaud, Pierre, et al.
Published: (2025)

The formula for the completion time of project networks
by: Castejón-Limas, Manuel, et al.
Published: (2024)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
by: Johnson, Matthew, et al.
Published: (2022)

On the parameterized complexity of Broadcast Independence and Broadcast Packing
by: Dumont, Joanne, et al.
Published: (2026)

Local Homophily on Bicolored Graphs is $\mathbf{P}$-complete
by: Concha-Vega, Pablo
Published: (2026)

An almost complete $t$-intersection theorem for permutations
by: Kupavskii, Andrey
Published: (2024)

Faces in rectilinear drawings of complete graphs
by: Balko, Martin, et al.
Published: (2025)

A complete $t$-intersection theorem for families of spanning trees
by: Iarovikova, Elizaveta, et al.
Published: (2025)

A complete solution of the Erdős-Kleitman matching problem for $n\le 3s$
by: Kupavskii, Andrey, et al.
Published: (2025)

Study on (r,s)- Generalised Transformation Graphs, A Novel Perspective Based on Transformation Graphs
by: Ali, Parvez, et al.
Published: (2024)

The PPP-completeness of the Ward-Szabo theorem
by: Ishizuka, Takashi
Published: (2025)

Boxicity of Zero Divisor Graphs
by: Chandran, L. Sunil, et al.
Published: (2025)

Axioms for Distanceless Graph Partitioning
by: Willson, James, et al.
Published: (2023)

Playing Snake on a Graph
by: Graafsma, Denise, et al.
Published: (2025)

Robust Filter Design for Graph Signals
by: Testa, Lucia, et al.
Published: (2024)

Cops & Robber on Periodic Temporal Graphs
by: De Carufel, Jean-Lou, et al.
Published: (2024)

Convergence Properties of Dynamic Processes on Graphs
by: Horscroft, Timothy
Published: (2024)

Coloring and Recognizing Directed Interval Graphs
by: Gutowski, Grzegorz, et al.
Published: (2023)

Cartesian Prime Graphs and Cospectral Families
by: Bitragunta, Abhinav, et al.
Published: (2025)

Coloring Mixed and Directional Interval Graphs
by: Gutowski, Grzegorz, et al.
Published: (2022)

Mim-Width is paraNP-complete
by: Bergougnoux, Benjamin, et al.
Published: (2025)

The complete edge relaxation for binary polynomial optimization
by: Del Pia, Alberto, et al.
Published: (2025)

Recognizing Sumsets is NP-Complete
by: Abboud, Amir, et al.
Published: (2024)

Graph Theoretic Investigations on Inefficiencies in Network Models
by: Cenciarelli, Pietro, et al.
Published: (2016)

Turán Graphs, Stability Number, and Fibonacci Index
by: Bruyère, Véronique, et al.
Published: (2008)

Algorithmic methods of finite discrete structures. Hamiltonian cycle of a complete graph and the Traveling salesman problem
by: Kurapov, Sergey, et al.
Published: (2024)

Graph drawing applications in combinatorial theory of maturity models
by: Kajzer, Špela, et al.
Published: (2024)

How to Color Temporal Graphs to Ensure Proper Transitions
by: Ibiapina, Allen, et al.
Published: (2025)

A Weight Function Lemma Heuristic for Graph Pebbling
by: Bridi, G. A., et al.
Published: (2025)

Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs
by: Friedrich, Tobias, et al.
Published: (2023)

Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
by: Dorfer, Joseph
Published: (2026)