Thumbnail - Request a copy

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

Cazals, Pierre; Darties, Benoit; Chateau, Annie; Giroudeau, Rodolphe; Weller, Mathias (2019), Power Edge Set and Zero Forcing Set Remain Difficult in Cubic Graphs, in Colbourn, Charles J.; Grossi, Roberto; Pisanti, Nadia, IWOCA 2019, Springer : Berlin Heidelberg, p. 122-135. 10.1007/978-3-030-25005-8_11

Type
Communication / Conférence
Date
2019
Conference title
Combinatorial Algorithms 30th International Workshop, IWOCA 2019, Pisa, Italy, July 23–25, 2019, Proceedings
Conference date
2019
Conference city
Berlin Heidelberg
Conference country
ITALY
Book title
IWOCA 2019
Book author
Colbourn, Charles J.; Grossi, Roberto; Pisanti, Nadia
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-030-25004-1
Pages
122-135
Publication identifier
Metadata
Show full item record
Author(s)
Cazals, Pierre
Darties, Benoit
Chateau, Annie
Giroudeau, Rodolphe
Weller, Mathias
Abstract (EN)
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.
Subjects / Keywords
Synchrophasor; Power Edge Set; Zero Forcing Set; Complexity