Problem med grafmodifiering kräver vanligtvis en liten uppsättning operationer som omvandlar en given graf för att ha en viss egenskap. De vanligaste åtgärderna inkluderar vertex radering, kantradering och kant addition; för samma egenskap kan man definiera betydligt olika versioner genom att tillåta olika operationer. Vi studerar en mycket allmän graf modifiering problem som tillåter alla tre typer av åtgärder: med tanke på en graf G och heltal k 1, k 2, och k 3, frågan ackord redigering problem om G kan omvandlas till en ackordkurva genom att som mest k 1 vertex raderingar, k 2 kant raderingar, och k 3 kant tillägg. Det är tydligt att detta problem generaliserar både ackordsutplåning och ackordkomplettering (även känd som minimal fyllning). Vårt huvudresultat är en algoritm för ackordredigering i tid 2 O(k log k) · n O(1), där k := k 1 + k 2 + k 3 och n är antalet hörn av G. Därför är problemet fast-parameter dragbar parameteriserad av det totala antalet tillåtna operationer. Vår algoritm är både effektivare och konceptuellt enklare än den tidigare kända algoritmen för den speciella fallkorset radering.
Cao och Marx REF studerar en generalisering av Chordal Complete, där tre operationer är tillåtna: vertex-radering, kanttillägg och kantradering.
Chordal Editing is Fixed-Parameter Tractable
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}