Datensatz Zitierlink: 
http://hdl.handle.net/20.500.12708/191195
-
Titel: 
The st-Planar Edge Completion Problem Is Fixed-Parameter Tractable
en
Zitat: 
Khazaliya, L., Kindermann, P., Liotta, G., Montecchiani, F., & Simonov, K. (2023). The st-Planar Edge Completion Problem Is Fixed-Parameter Tractable. In S. Iwata & N. Kakimura (Eds.), 34th International Symposium on Algorithms and Computation (ISAAC 2023) (pp. 1–13). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ISAAC.2023.46
-
Verlags-DOI: 
10.4230/LIPICS.ISAAC.2023.46
-
Publikationstyp: 
Konferenzbeitrag - Full-Paper Contribution
de
Sprache: 
Englisch
-
Autor_innen: 
Khazaliya, Liana 
Kindermann, Philipp 
Liotta, Giuseppe 
Montecchiani, Fabrizio 
Simonov, Kirill 
-
Organisations­einheit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Erschienen in: 
34th International Symposium on Algorithms and Computation (ISAAC 2023) 
-
ISBN: 
978-3-95977-289-1
-
Band: 
283
-
Datum (veröffentlicht): 
Dez-2023
-
Veranstaltungs­name: 
34th International Symposium on Algorithms and Computation (ISAAC 2023) 
en
Veranstaltungs­zeitraum: 
3-Dez-2023 - 6-Dez-2023
-
Veranstaltungs­ort: 
Kyoto, Japan
-
Umfang: 
13
-
Verlag: 
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
-
Peer Reviewed: 
Ja
-
Keywords: 
st-planar graphs; parameterized complexity; Upward planarity
en
Abstract: 
The problem of deciding whether a biconnected planar digraph G = (V, E) can be augmented to become an st-planar graph by adding a set of oriented edges E′ ⊆ V ×V is known to be NP-complete. We show that the problem is fixed-parameter tractable when parameterized by the size of the set E′
en
Forschungs­schwerpunkte: 
Logic and Computation: 100%
-
Wissenschafts­zweig: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Enthalten in den Sammlungen:
Conference Paper

Zur Langanzeige

Seiten Aufrufe

251
aufgerufen am 06.01.2024

Google ScholarTM

Check