Planar Steiner Orientation is NP-complete

Cite This

Files in this item

Checksum: MD5:7a62bd2c1fd5cc44cd29d7dbbdaafcb6

BECK, Moritz, Johannes BLUM, Myroslav KRYVEN, Andre LÖFFLER, Johannes ZINK, 2018. Planar Steiner Orientation is NP-complete

@unpublished{Beck2018-04-20T08:57:39ZPlana-44518, title={Planar Steiner Orientation is NP-complete}, year={2018}, author={Beck, Moritz and Blum, Johannes and Kryven, Myroslav and Löffler, Andre and Zink, Johannes} }

<rdf:RDF xmlns:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <dc:contributor>Blum, Johannes</dc:contributor> <dc:creator>Beck, Moritz</dc:creator> <dcterms:rights rdf:resource=""/> <dc:rights>terms-of-use</dc:rights> <dc:date rdf:datatype="">2019-01-10T15:01:26Z</dc:date> <dc:creator>Zink, Johannes</dc:creator> <dc:creator>Blum, Johannes</dc:creator> <dc:contributor>Beck, Moritz</dc:contributor> <dcterms:hasPart rdf:resource=""/> <dcterms:abstract xml:lang="eng">Many applications in graph theory are motivated by routing or flow problems. Among these problems is Steiner Orientation: given a mixed graph G (having directed and undirected edges) and a set T of k terminal pairs in G, is there an orientation of the undirected edges in G such that there is a directed path for every terminal pair in T ? This problem was shown to be NP -complete by Arkin and Hassin and later W [1]-hard by Pilipczuk and Wahlström, parametrized by k. On the other hand, there is an XP algorithm by Cygan et al. and a polynomial time algorithm for graphs without directed edges by Hassin and Megiddo. Chitnis and Feldmann showed W [1]-hardness of the problem for graphs of genus 1. We consider a further restriction to planar graphs and show NP -completeness.</dcterms:abstract> <dcterms:title>Planar Steiner Orientation is NP-complete</dcterms:title> <dc:creator>Kryven, Myroslav</dc:creator> <dcterms:isPartOf rdf:resource=""/> <dspace:isPartOfCollection rdf:resource=""/> <dc:contributor>Löffler, Andre</dc:contributor> <dc:creator>Löffler, Andre</dc:creator> <dc:contributor>Kryven, Myroslav</dc:contributor> <dc:contributor>Zink, Johannes</dc:contributor> <dcterms:issued>2018-04-20T08:57:39Z</dcterms:issued> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dspace:hasBitstream rdf:resource=""/> <dcterms:available rdf:datatype="">2019-01-10T15:01:26Z</dcterms:available> <dc:language>eng</dc:language> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <bibo:uri rdf:resource=""/> </rdf:Description> </rdf:RDF>

Downloads since Jan 10, 2019 (Information about access statistics)

Beck_2-b4bo2o1xb2qr0.pdf 672

This item appears in the following Collection(s)

Search KOPS


My Account