Power Edge Set and Zero Forcing Set Remain Difficult in Cubic Graphs - ESIEE Paris Access content directly
Conference Papers Year : 2019

Power Edge Set and Zero Forcing Set Remain Difficult in Cubic Graphs

Abstract

This paper presents new complexity and non-approximation results concerning two color propagation problems, namely Power Edge Set and Zero Forcing Set. We focus on cubic graphs, exploiting their structural properties to improve and refine previous results. We also give hardness results for parameterized precolored versions of these problems, and a polynomial-time algorithm for Zero Forcing Set in proper interval graphs.
Fichier principal
Vignette du fichier
main.pdf (477.77 Ko) Télécharger le fichier
Origin Files produced by the author(s)
licence

Dates and versions

hal-02359076 , version 1 (09-06-2024)

Licence

Identifiers

Cite

Pierre Cazals, Benoit Darties, Annie Chateau, Rodolphe Giroudeau, Mathias Weller. Power Edge Set and Zero Forcing Set Remain Difficult in Cubic Graphs. IWOCA 2019 - 30th International Workshop on Combinatorial Algorithms, Jul 2019, Pisa, Italy. pp.122-135, ⟨10.1007/978-3-030-25005-8_11⟩. ⟨hal-02359076⟩
113 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More