Vi undersöker problemet med vertex-radering för viktade riktade acykliska grafer (wdags). Målet är att ta bort det minsta antalet hörn så att den resulterande onsdagen inte har någon väg av längd > δ. Flera förenklade versioner av detta problem visar sig vara NP-hårda. Problemet löses dock i linjär tid när wdag är ett rotat träd och i kvadratisk tid när wdag är en serie-parallell graf.
För vertex-radering av DED(k), Paik et al. REF gav linjära tids- och andragradsalgoritmer för rotade träd respektive serieparallelldiagram.
Deleting Vertices to Bound Path Length
{'venue': 'IEEE Trans. Computers', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}