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

@techreport{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="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/44518"> <dc:contributor>Blum, Johannes</dc:contributor> <dc:creator>Beck, Moritz</dc:creator> <dc:rights>terms-of-use</dc:rights> <dcterms:rights rdf:resource="https://kops.uni-konstanz.de/page/termsofuse"/> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">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="https://kops.uni-konstanz.de/bitstream/123456789/44518/3/Beck_2-b4bo2o1xb2qr0.pdf"/> <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="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <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="https://kops.uni-konstanz.de/bitstream/123456789/44518/3/Beck_2-b4bo2o1xb2qr0.pdf"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-10T15:01:26Z</dcterms:available> <dc:language>eng</dc:language> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44518"/> </rdf:Description> </rdf:RDF>

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

Beck_2-b4bo2o1xb2qr0.pdf 494

This item appears in the following Collection(s)

Search KOPS


Browse

My Account