Idioma:

Algorithms and obstructions for linear-width and related search parameters

Thilikos, Dimitrios M.

Discrete Applied Mathematics, 2000-10, Vol.105 (1), p.239-271 [Periódico revisado por pares]

Lausanne: Elsevier B.V

Texto completo disponível

Citações Citado por

Enviar para

Título:
Algorithms and obstructions for linear-width and related search parameters
Autor: Thilikos, Dimitrios M.
Assuntos: Applied sciences ; Combinatorics ; Combinatorics. Ordered structures ; Computer science; control theory; systems ; Exact sciences and technology ; Graph algorithm ; Graph minor ; Graph searching ; Graph theory ; Information retrieval. Graph ; Linear width ; Mathematics ; Obstruction set ; Sciences and techniques of general use ; Theoretical computing
É parte de: Discrete Applied Mathematics, 2000-10, Vol.105 (1), p.239-271
Descrição: The linear-width of a graph G is defined to be the smallest integer k such that the edges of G can be arranged in a linear ordering ( e 1,…, e r ) in such a way that for every i=1,…, r−1, there are at most k vertices incident to edges that belong both to { e 1,…, e i } and to { e i+1 ,…, e r }. In this paper, we give a set of 57 graphs and prove that it is the set of the minimal forbidden minors for the class of graphs with linear-width at most two. Our proof also gives a linear time algorithm that either reports that a given graph has linear-width more than two or outputs an edge ordering of minimum linear-width. We further prove a structural connection between linear-width and the mixed search number which enables us to determine, for any k⩾1, the set of acyclic forbidden minors for the class of graphs with linear-width⩽ k. Moreover, due to this connection, our algorithm can be transfered to two linear time algorithms that check whether a graph has mixed search or edge search number at most two and, if so, construct the corresponding sequences of search moves.
Editor: Lausanne: Elsevier B.V
Idioma: Inglês

Links

View record in Pascal Francis

Voltar para lista de resultados

Realização: Logos de Redes Sociais:

Algorithms and obstructions for linear-width and related search parameters

Thilikos, Dimitrios M.

Lausanne: Elsevier B.V

Buscando em bases de dados remotas. Favor aguardar.