Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-43659
Titel: | An FPT Algorithm for Directed Co-Graph Edge Deletion |
VerfasserIn: | Li, Wenjun Yang, Xueying Xu, Chao Yang, Yongjie |
Sprache: | Englisch |
Titel: | Algorithms |
Bandnummer: | 17 |
Heft: | 2 |
Verlag/Plattform: | MDPI |
Erscheinungsjahr: | 2024 |
Freie Schlagwörter: | edge deletion FPT algorithms directed co-graphs forbidden structures |
DDC-Sachgruppe: | 330 Wirtschaft |
Dokumenttyp: | Journalartikel / Zeitschriftenartikel |
Abstract: | In the directed co-graph edge-deletion problem, we are given a directed graph and an integer k, and the question is whether we can delete, at most, k edges so that the resulting graph is a directed co-graph. In this paper, we make two minor contributions. Firstly, we show that the problem is NP-hard. Then, we show that directed co-graphs are fully characterized by eight forbidden structures, each having, at most, six edges. Based on the symmetry properties and several refined observations, we develop a branching algorithm with a running time of đ(2.733đ), which is significantly more efficient compared to the brute-force algorithm, which has a running time of đ(6đ). |
DOI der Erstveröffentlichung: | 10.3390/a17020069 |
URL der Erstveröffentlichung: | https://www.mdpi.com/1999-4893/17/2/69 |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291--ds-436598 hdl:20.500.11880/39128 http://dx.doi.org/10.22028/D291-43659 |
ISSN: | 1999-4893 |
Datum des Eintrags: | 6-Dez-2024 |
FakultĂ€t: | HW - FakultĂ€t fĂŒr Empirische Humanwissenschaften und Wirtschaftswissenschaft |
Fachrichtung: | HW - Wirtschaftswissenschaft |
Professur: | HW - Prof. Dr. Dinko Dimitrov |
Sammlung: | SciDok - Der Wissenschaftsserver der UniversitÀt des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | GröĂe | Format | |
---|---|---|---|---|
algorithms-17-00069.pdf | 290,59 kB | Adobe PDF | Ăffnen/Anzeigen |
Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons