Idioma:

INTRACTABILITY OF CLIQUE-WIDTH PARAMETERIZATIONS

FOMIN, Fedor V ; GOLOVACH, Petr A ; LOKSHTANOV, Daniel ; SAURABH, Saket

SIAM journal on computing, 2010, Vol.39 (5), p.1941-1956 [Periódico revisado por pares]

Philadelphia, PA: Society for Industrial and Applied Mathematics

Texto completo disponível

Citações Citado por

Enviar para

Título:
INTRACTABILITY OF CLIQUE-WIDTH PARAMETERIZATIONS
Autor: FOMIN, Fedor V ; GOLOVACH, Petr A ; LOKSHTANOV, Daniel ; SAURABH, Saket
Assuntos: Algorithmics. Computability. Computer arithmetics ; Algorithms ; Applied sciences ; Combinatorics ; Combinatorics. Ordered structures ; Complexity theory ; Computation ; Computer science; control theory; systems ; Exact sciences and technology ; Graph coloring ; Graph theory ; Graphs ; Mathematical analysis ; Mathematical models ; Mathematics ; Miscellaneous ; Parameter optimization ; Parametrization ; Running ; Sciences and techniques of general use ; Studies ; Symbols ; Theoretical computing
É parte de: SIAM journal on computing, 2010, Vol.39 (5), p.1941-1956
Notas: ObjectType-Article-1
SourceType-Scholarly Journals-1
ObjectType-Feature-2
content type line 23
Descrição: The authors show that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are ... parameterized by clique-width. It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, that is, solvable in time ... on n-vertex graphs of clique-width k, where g is some function of k only. The results imply that the running time ... of many clique-width-based algorithms is essentially the best they can hope for (up to a widely believed assumption from parameterized complexity, namely ... ).(ProQuest: ... denotes formulae/symbols omitted.)
Editor: Philadelphia, PA: Society for Industrial and Applied Mathematics
Idioma: Inglês

Links

View record in Pascal Francis

Voltar para lista de resultados

Realização: Logos de Redes Sociais:

INTRACTABILITY OF CLIQUE-WIDTH PARAMETERIZATIONS

FOMIN, Fedor V ; GOLOVACH, Petr A ; LOKSHTANOV, Daniel ; SAURABH, Saket

Philadelphia, PA: Society for Industrial and Applied Mathematics

Buscando em bases de dados remotas. Favor aguardar.