We show that the firefighter problem is NP-complete for trees of maximum degree three, but in P for graphs of maximum degree three if the fire breaks out at a vertex of degree at most two.

The firefighter problem for graphs of maximum degree three

RIZZI, ROMEO
2007-01-01

Abstract

We show that the firefighter problem is NP-complete for trees of maximum degree three, but in P for graphs of maximum degree three if the fire breaks out at a vertex of degree at most two.
2007
Firefigher problem
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/409539
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 91
  • ???jsp.display-item.citation.isi??? 77
social impact