More Results on the Complexity of Identifying Problems in Graphs

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 metadatas

https://hal.telecom-paristech.fr/hal-02287134
Contributor : Telecomparis Hal <>
Submitted on : Friday, September 13, 2019 - 4:37:58 PM
Last modification on : Sunday, September 15, 2019 - 1:11:41 AM

Identifiers

  • HAL Id : hal-02287134, version 1

Citation

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

Share

Metrics

Record views

7