skip to main content

Parameterized complexity of connected even/odd subgraph problems

Fomin, Fedor V ; Golovach, Petr A

Journal of Computer and System Sciences, February 2014, Vol.80(1), pp.157-179 [Periódico revisado por pares]

Texto completo disponível

Ver todas as versões
Citações Citado por
  • Título:
    Parameterized complexity of connected even/odd subgraph problems
  • Autor: Fomin, Fedor V ; Golovach, Petr A
  • Assuntos: Parameterized Complexity ; Euler Graph ; Even Graph ; Odd Graph ; Treewidth ; Engineering ; Computer Science
  • É parte de: Journal of Computer and System Sciences, February 2014, Vol.80(1), pp.157-179
  • Descrição: In 2011, Cai an Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs: for a given graph and integer , the task is to decide if contains a (connected) subgraph with vertices (edges) with all vertices of even (odd) degrees. They succeed to establish the parameterized complexity of all cases except two, when we ask about: We show that - is FPT and - is -hard. Our FPT algorithm is based on a novel combinatorial result on the treewidth of minimal connected odd graphs with even amount of edges.
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.