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Ă¶ĂŸeFormat 
algorithms-17-00069.pdf290,59 kBAdobe PDFÖffnen/Anzeigen


Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons Creative Commons