Planar Steiner Orientation is NP-complete
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
ArXiv-ID
Internationale Patentnummer
Link zur Lizenz
EU-Projektnummer
DFG-Projektnummer
Projekt
Open Access-Veröffentlichung
Sammlungen
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
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.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
BECK, Moritz, Johannes BLUM, Myroslav KRYVEN, Andre LÖFFLER, Johannes ZINK, 2018. Planar Steiner Orientation is NP-completeBibTex
@unpublished{Beck2018-04-20T08:57:39ZPlana-44518, year={2018}, title={Planar Steiner Orientation is NP-complete}, author={Beck, Moritz and Blum, Johannes and Kryven, Myroslav and Löffler, Andre and Zink, Johannes} }
RDF
<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/server/rdf/resource/123456789/44518"> <dc:rights>terms-of-use</dc:rights> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-10T15:01:26Z</dcterms:available> <dcterms:title>Planar Steiner Orientation is NP-complete</dcterms:title> <dc:creator>Blum, Johannes</dc:creator> <foaf:homepage rdf:resource="http://localhost:8080/"/> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44518"/> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:contributor>Zink, Johannes</dc:contributor> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-01-10T15:01:26Z</dc:date> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/44518/3/Beck_2-b4bo2o1xb2qr0.pdf"/> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/44518/3/Beck_2-b4bo2o1xb2qr0.pdf"/> <dc:creator>Zink, Johannes</dc:creator> <dcterms:issued>2018-04-20T08:57:39Z</dcterms:issued> <dc:creator>Löffler, Andre</dc:creator> <dc:creator>Kryven, Myroslav</dc:creator> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:creator>Beck, Moritz</dc:creator> <dc:language>eng</dc:language> <dc:contributor>Löffler, Andre</dc:contributor> <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> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:contributor>Blum, Johannes</dc:contributor> <dc:contributor>Kryven, Myroslav</dc:contributor> <dc:contributor>Beck, Moritz</dc:contributor> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> </rdf:Description> </rdf:RDF>