Descriptive complexity of controllable graphs

Aida Abiad, Anuj Dawar, Octavio Zapata (Corresponding author)

Onderzoeksoutput: Bijdrage aan tijdschriftCongresartikelpeer review

29 Downloads (Pure)

Samenvatting

Let G be a graph on n vertices with adjacency matrix A, and let 1 be the all-ones vector. We call G controllable if the set of vectors 1, A1,., An-11 spans the whole space Rn. We characterize the isomorphism problem of controllable graphs in terms of other combinatorial, geometric and logical problems. We also describe a polynomial time algorithm for graph isomorphism that works for almost all graphs.

Originele taal-2Engels
Pagina's (van-tot)20-27
Aantal pagina's8
TijdschriftProcedia Computer Science
Volume223
DOI's
StatusGepubliceerd - 2023
Evenement12th Latin-American Algorithms, Graphs and Optimization Symposium, LAGOS 2023 - Huatulco, Mexico
Duur: 18 sep. 202322 sep. 2023

Financiering

The research of A. Abiad is partially supported by the FWO grant 1285921N. The research of O. Zapata is partially supported by the SNI grant 620178.

FinanciersFinanciernummer
Fonds Wetenschappelijk Onderzoek1285921N

    Vingerafdruk

    Duik in de onderzoeksthema's van 'Descriptive complexity of controllable graphs'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit