Publikation:

A note on the practicality of maximal planar subgraph algorithms

Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2016

Autor:innen

Chimani, Markus
Wiedera, Tilo

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
DOI (zitierfähiger Link)
https://doi.org/10.1007/978-3-319-50106-2_28
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen 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. Cham: Springer International Publishing - Springer, 2016, pp. 357-364. Lecture Notes in Computer Science. 9801. ISBN 978-3-319-50105-5. Available under: doi: 10.1007/978-3-319-50106-2_28

Zusammenfassung

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.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

International Symposium on Graph Drawing and Network Visualization, 19. Sept. 2016 - 21. Sept. 2016, Athens, Greece
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690CHIMANI, 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. Sept. 2016 - 21. Sept. 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. Cham: Springer International Publishing - Springer, 2016, pp. 357-364. Lecture Notes in Computer Science. 9801. ISBN 978-3-319-50105-5. Available under: doi: 10.1007/978-3-319-50106-2_28
BibTex
@inproceedings{Chimani2016pract-36860,
  year={2016},
  doi={10.1007/978-3-319-50106-2_28},
  title={A note on the practicality of maximal planar subgraph algorithms},
  number={9801},
  isbn={978-3-319-50105-5},
  publisher={Springer International Publishing - Springer},
  address={Cham},
  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: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/36860">
    <dc:creator>Chimani, Markus</dc:creator>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/36860"/>
    <dc:creator>Wiedera, Tilo</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <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>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-01-20T10:00:47Z</dc:date>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Wiedera, Tilo</dc:contributor>
    <dcterms:issued>2016</dcterms:issued>
    <dc:creator>Klein, Karsten</dc:creator>
    <dcterms:title>A note on the practicality of maximal planar subgraph algorithms</dcterms:title>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2017-01-20T10:00:47Z</dcterms:available>
    <dc:contributor>Chimani, Markus</dc:contributor>
    <dc:contributor>Klein, Karsten</dc:contributor>
    <dc:language>eng</dc:language>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen