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érenceDate
2019Conference title
Combinatorial Algorithms 30th International Workshop, IWOCA 2019, Pisa, Italy, July 23–25, 2019, ProceedingsConference date
2019Conference city
Berlin HeidelbergConference country
ITALYBook title
IWOCA 2019Book author
Colbourn, Charles J.; Grossi, Roberto; Pisanti, NadiaPublisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-030-25004-1
Pages
122-135
Publication identifier
Metadata
Show full item recordAbstract (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; ComplexityRelated items
Showing items related by title and author.
-
Cazals, Pierre (2021-12-10) Thèse
-
Toubaline, Sónia; D’Ambrosio, Claudia; Liberti, Leo; Poirion, Pierre-Louis; Schieber, Baruch; Shachnai, Hadas (2018) Article accepté pour publication ou publié
-
Bazgan, Cristina; Cazals, Pierre; Chlebíková, Janka (2020) Communication / Conférence
-
Bazgan, Cristina; Casel, Katrin; Cazals, Pierre (2022) Communication / Conférence
-
Benkouar, A.; Manoussakis, Yannis; Paschos, Vangelis; Saad, Rachid (1996) Article accepté pour publication ou publié