Idioma:

Shrub-depth: Capturing Height of Dense Graphs

Ossona de Mendez, Patrice ; Ganian, Robert ; Hliněný, Petr ; Nešetřil, Jaroslav ; Obdrzalek, Jan

Logical methods in computer science, 2019, Vol.15 (1) [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
Shrub-depth: Capturing Height of Dense Graphs
Autor: Ossona de Mendez, Patrice ; Ganian, Robert ; Hliněný, Petr ; Nešetřil, Jaroslav ; Obdrzalek, Jan
Assuntos: 03b70, 05c75, 68r10 ; Combinatorics ; computer science - discrete mathematics ; computer science - logic in computer science ; Mathematics ; mathematics - combinatorics
É parte de: Logical methods in computer science, 2019, Vol.15 (1)
Descrição: The recent increase of interest in the graph invariant called tree-depth and in its applications in algorithms and logic on graphs led to a natural question: is there an analogously useful "depth" notion also for dense graphs (say; one which is stable under graph complementation)? To this end, in a 2012 conference paper, a new notion of shrub-depth has been introduced, such that it is related to the established notion of clique-width in a similar way as tree-depth is related to tree-width. Since then shrub-depth has been successfully used in several research papers. Here we provide an in-depth review of the definition and basic properties of shrub-depth, and we focus on its logical aspects which turned out to be most useful. In particular, we use shrub-depth to give a characterization of the lower ${\omega}$ levels of the MSO1 transduction hierarchy of simple graphs.
Editor: Logical Methods in Computer Science Association
Idioma: Inglês

Links

Voltar para lista de resultados

Anterior Resultado 5 Avançar Ir para próxima página