Vi studerar problemet Minimum Length-Bounded Cut där uppgiften är att hitta en uppsättning kanter av en graf så att efter avlägsnande av denna uppsättning, den kortaste vägen mellan två föreskrivna hörn är minst L + 1 lång. Vi visar problemet kan beräknas i FPT tid med avseende på L och trädbredden av ingångsgraf G som parametrar och med linjärt beroende av Vi härleda en FPT algoritm för en mer allmän multi-commodity längd bundna skär problem när dessutom parameteriseras av antalet terminaler. För det tidigare problemet visar vi ett W[1]-hårdhet resultat när parameteriseringen görs av vägbredden endast (istället för trädbredden) och att detta problem inte medger polynom kärnan när parameteriserats av vägbredd och L. Vi härleder också en FPT algoritm för minsta längd-Bounded Cut problem när parameterized av träddjupet, vilket visar ett intressant beteende för detta problem och parametrar träddjup och bana-bredd.
Dvořák och Knop REF beaktade strukturella parametrar för problemet med långväga skär.
Parameterized Complexity of Length-bounded Cuts and Multicuts
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}