A note on the practicality of maximal planar subgraph algorithms

Zitieren

Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

CHIMANI, Markus, Karsten KLEIN, Tilo WIEDERA, 2016. A note on the practicality of maximal planar subgraph algorithms. International Symposium on Graph Drawing and Network Visualization. Athens, Greece, 19. Sep 2016 - 21. Sep 2016. In: HU, Yifan, ed., Martin NÖLLENBURG, ed.. Graph Drawing and Network Visualization : 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers. International Symposium on Graph Drawing and Network Visualization. Athens, Greece, 19. Sep 2016 - 21. Sep 2016. Cham:Springer International Publishing - Springer, pp. 357-364. ISBN 978-3-319-50105-5

@inproceedings{Chimani2016pract-36860, title={A note on the practicality of maximal planar subgraph algorithms}, year={2016}, doi={10.1007/978-3-319-50106-2_28}, number={9801}, isbn={978-3-319-50105-5}, address={Cham}, publisher={Springer International Publishing - Springer}, series={Lecture Notes in Computer Science}, booktitle={Graph Drawing and Network Visualization : 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers}, pages={357--364}, editor={Hu, Yifan and Nöllenburg, Martin}, author={Chimani, Markus and Klein, Karsten and Wiedera, Tilo} }

<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:dcterms="http://purl.org/dc/terms/" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/36860"> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-01-20T10:00:47Z</dc:date> <dc:creator>Wiedera, Tilo</dc:creator> <dcterms:abstract xml:lang="eng">Given a graph G, the NP-hard Maximum Planar Subgraph problem (MPS) asks for a planar subgraph of G with the maximum number of edges. There are several heuristic, approximative, and exact algorithms to tackle the problem, but—to the best of our knowledge—they have never been compared competitively in practice. We report on an exploratory study on the relative merits of the diverse approaches, focusing on practical runtime, solution quality, and implementation complexity. Surprisingly, a seemingly only theoretically strong approximation forms the building block of the strongest choice.</dcterms:abstract> <dc:creator>Chimani, Markus</dc:creator> <dc:language>eng</dc:language> <dc:contributor>Wiedera, Tilo</dc:contributor> <dcterms:title>A note on the practicality of maximal planar subgraph algorithms</dcterms:title> <dc:contributor>Chimani, Markus</dc:contributor> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-01-20T10:00:47Z</dcterms:available> <dc:creator>Klein, Karsten</dc:creator> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/36860"/> <dc:contributor>Klein, Karsten</dc:contributor> <dcterms:issued>2016</dcterms:issued> </rdf:Description> </rdf:RDF>

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto