Vi visar att brandmännens problem är NP-komplett för kubikdiagram. Vi visar också att med tanke på ett rotat träd av maximal grad tre där varje blad är samma avstånd från roten, är det NPfullständigt att avgöra om det finns en strategi som skyddar varje blad från elden, som börjar vid roten. Däremot beskriver vi en polynom tid algoritm för att avgöra om det är möjligt att spara en given delmängd av hörnen i en graf med maximal grad tre, förutsatt att elden bryter ut vid en vertex av grad högst två.
REF visade att för ett träd av grad högst 3, det är NP-hård att spara en kritisk uppsättning med budgeten för en brandman per runda, men är polynom tid när branden börjar från en vertex av grad högst 2.
The Firefighter Problem For Cubic Graphs
{'venue': 'Discret. Math.', 'journal': 'Discret. Math.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}