Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Journal articles

More Results on the Complexity of Identifying Problems in Graphs

Olivier Hudry 1, 2 Antoine Lobstein 1, 2 
Abstract : We investigate the complexity of several problems linked with identification in graphs, such as, given an integer r >= 1 and a graph G = (V;E), the existence of, or search for, optimal r-identifying codes in G, or optimal r-identifying codes in G containing a given subset of vertices. We locate these problems in the complexity classes of the polynomial hierarchy.
Complete list of metadata
Contributor : TelecomParis HAL Connect in order to contact the contributor
Submitted on : Friday, September 13, 2019 - 4:37:58 PM
Last modification on : Monday, January 24, 2022 - 8:26:29 AM


  • HAL Id : hal-02287134, version 1


Olivier Hudry, Antoine Lobstein. More Results on the Complexity of Identifying Problems in Graphs. Theoretical Computer Science, Elsevier, 2016, 626, pp.1-12. ⟨hal-02287134⟩



Record views