<div class="csl-bib-body">
<div class="csl-entry">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.), <i>34th International Symposium on Algorithms and Computation (ISAAC 2023)</i> (pp. 1–13). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ISAAC.2023.46</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/191195
-
dc.description.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
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics : LIPIcs
-
dc.subject
st-planar graphs
en
dc.subject
parameterized complexity
en
dc.subject
Upward planarity
en
dc.title
The st-Planar Edge Completion Problem Is Fixed-Parameter Tractable
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
Universität Trier, Germany
-
dc.contributor.affiliation
University of Perugia, Italy
-
dc.contributor.affiliation
University of Perugia, Italy
-
dc.contributor.affiliation
University of Potsdam, Germany
-
dc.relation.isbn
978-3-95977-289-1
-
dc.description.startpage
1
-
dc.description.endpage
13
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
1868-8969
-
tuw.booktitle
34th International Symposium on Algorithms and Computation (ISAAC 2023)
-
tuw.container.volume
283
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
-
tuw.book.chapter
46
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publisher.doi
10.4230/LIPICS.ISAAC.2023.46
-
dc.description.numberOfPages
13
-
tuw.author.orcid
0009-0002-3012-7240
-
tuw.author.orcid
0000-0002-2886-9694
-
tuw.editor.orcid
0000-0002-3918-3479
-
tuw.event.name
34th International Symposium on Algorithms and Computation (ISAAC 2023)
en
tuw.event.startdate
03-12-2023
-
tuw.event.enddate
06-12-2023
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Kyoto
-
tuw.event.country
JP
-
tuw.event.presenter
Simonov, Kirill
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.grantfulltext
none
-
item.fulltext
no Fulltext
-
item.languageiso639-1
en
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.cerifentitytype
Publications
-
item.openairetype
conference paper
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
Universität Trier
-
crisitem.author.dept
University of Perugia
-
crisitem.author.dept
University of Perugia
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
