Record link: 
http://hdl.handle.net/20.500.12708/191195
-
Title: 
The st-Planar Edge Completion Problem Is Fixed-Parameter Tractable
en
Citation: 
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
-
Publisher DOI: 
10.4230/LIPICS.ISAAC.2023.46
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Khazaliya, Liana 
Kindermann, Philipp 
Liotta, Giuseppe 
Montecchiani, Fabrizio 
Simonov, Kirill 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
34th International Symposium on Algorithms and Computation (ISAAC 2023) 
-
ISBN: 
978-3-95977-289-1
-
Volume: 
283
-
Date (published): 
Dec-2023
-
Event name: 
34th International Symposium on Algorithms and Computation (ISAAC 2023) 
en
Event date: 
3-Dec-2023 - 6-Dec-2023
-
Event place: 
Kyoto, Japan
-
Number of Pages: 
13
-
Publisher: 
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
-
Peer reviewed: 
Yes
-
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
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

309
checked on Jan 6, 2024

Google ScholarTM

Check