Contents

Journal of Combinatorial Mathematics and Combinatorial Computing

  • Research article

On the Firefighter Problem

Gary MacGillivray1, Ping Wang2
1Department of Mathematics and Statistics University of Victoria Victoria, British Columbia, Canada
2Department of Mathematics, Statistics and Computer Science St. Francis Xavier University, Antigonish, Nova Scotia, Canada
  • Published: 30/11/2003

Abstract

We consider the firefighter problem. We begin by proving that the associated decision problem is NP-complete even when restricted to bipartite graphs. We then investigate algorithms and bounds for trees and square grids.

Information
Guidelines
CP Initiatives
Follow CP
Facebook X-twitter Linkedin

1970-2025 CP (Manitoba, Canada) unless otherwise stated.

Citation
Gary MacGillivray, Ping Wang. On the Firefighter Problem[J], Journal of Combinatorial Mathematics and Combinatorial Computing, Volume 047. 83-96. DOI: .