• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
10.1007/978-3-030-25005-8_11
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

Related items

Showing items related by title and author.

  • Thumbnail
    Communities and anonymization in graphs 
    Cazals, Pierre (2021-12-10) Thèse
  • Thumbnail
    Complexity and inapproximability results for the Power Edge Set problem 
    Toubaline, Sónia; D’Ambrosio, Claudia; Liberti, Leo; Poirion, Pierre-Louis; Schieber, Baruch; Shachnai, Hadas (2018) Article accepté pour publication ou publié
  • Thumbnail
    How to Get a Degree-Anonymous Graph Using Minimum Number of Edge Rotations 
    Bazgan, Cristina; Cazals, Pierre; Chlebíková, Janka (2020) Communication / Conférence
  • Thumbnail
    Dense Graph Partitioning on Sparse and Dense Graphs 
    Bazgan, Cristina; Casel, Katrin; Cazals, Pierre (2022) Communication / Conférence
  • Thumbnail
    Hamiltonian problems in edge-colored complete graphs and Eulerian cycles in edge-colored graphs: some complexity results 
    Benkouar, A.; Manoussakis, Yannis; Paschos, Vangelis; Saad, Rachid (1996) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo