Publikation:

PlaNet : A Software Package of Algorithms and Heuristics on Planar Networks

Lade...
Vorschaubild

Dateien

PlaNet.pdf
PlaNet.pdfGröße: 371.78 KBDownloads: 810

Datum

1999

Autor:innen

Neyer, Gabriele
Schickenrieder, Wolfram
Wagner, Dorothea
Weihe, Karsten

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Zeitschriftenartikel
Publikationsstatus
Published

Erschienen in

Discrete Applied Mathematics. 1999, 92(2-3), pp. 91-110. ISSN 0166-218X. eISSN 1872-6771. Available under: doi: 10.1016/S0166-218X(99)00048-7

Zusammenfassung

We present a package for algorithms on planar networks. This package comes with a graphical user interface, which may be used for demonstrating and animating algorithms. Our focus so far has been on disjoint path problems. However, the package is intended to serve as a general framework, wherein algorithms for various problems on planar networks may be integrated and visualized. For this aim, the structure of the package is designed so that integration of new algorithms and even new algorithmic problems amounts to applying a short "recipe". The package has been used to develop new variations of well--known disjoint path algorithms, which heuristically optimize additional NP--hard objectives such as the total length of all paths. We will prove that the problem of finding edge--disjoint paths of minimum total length in a planar graph is NP--hard, even if all terminals lie on the outer face, the Eulerian condition is fulfilled, and the maximum degree is four. Finally, we will report results of experimental studies on efficient heuristics for this problem.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690BRANDES, Ulrik, Gabriele NEYER, Wolfram SCHICKENRIEDER, Dorothea WAGNER, Karsten WEIHE, 1999. PlaNet : A Software Package of Algorithms and Heuristics on Planar Networks. In: Discrete Applied Mathematics. 1999, 92(2-3), pp. 91-110. ISSN 0166-218X. eISSN 1872-6771. Available under: doi: 10.1016/S0166-218X(99)00048-7
BibTex
@article{Brandes1999PlaNe-5854,
  year={1999},
  doi={10.1016/S0166-218X(99)00048-7},
  title={PlaNet : A Software Package of Algorithms and Heuristics on Planar Networks},
  number={2-3},
  volume={92},
  issn={0166-218X},
  journal={Discrete Applied Mathematics},
  pages={91--110},
  author={Brandes, Ulrik and Neyer, Gabriele and Schickenrieder, Wolfram and Wagner, Dorothea and Weihe, Karsten}
}
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/5854">
    <dc:contributor>Wagner, Dorothea</dc:contributor>
    <dc:contributor>Weihe, Karsten</dc:contributor>
    <dcterms:title>PlaNet : A Software Package of Algorithms and Heuristics on Planar Networks</dcterms:title>
    <dcterms:abstract xml:lang="eng">We present a package for algorithms on planar networks. This package comes with a graphical user interface, which may be used for demonstrating and animating algorithms. Our focus so far has been on disjoint path problems. However, the package is intended to serve as a general framework, wherein algorithms for various problems on planar networks may be integrated and visualized. For this aim, the structure of the package is designed so that integration of new algorithms and even new algorithmic problems amounts to applying a short "recipe". The package has been used to develop new variations of well--known disjoint path algorithms, which heuristically optimize additional NP--hard objectives such as the total length of all paths. We will prove that the problem of finding edge--disjoint paths of minimum total length in a planar graph is NP--hard, even if all terminals lie on the outer face, the Eulerian condition is fulfilled, and the maximum degree is four. Finally, we will report results of experimental studies on efficient heuristics for this problem.</dcterms:abstract>
    <dc:contributor>Schickenrieder, Wolfram</dc:contributor>
    <dcterms:issued>1999</dcterms:issued>
    <dc:creator>Neyer, Gabriele</dc:creator>
    <dcterms:bibliographicCitation>First publ. in: Discrete Applied Mathematics 92 (1999), 2-3, pp. 91-110</dcterms:bibliographicCitation>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Weihe, Karsten</dc:creator>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/5854"/>
    <dc:format>application/pdf</dc:format>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:42Z</dcterms:available>
    <dc:contributor>Neyer, Gabriele</dc:contributor>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5854/1/PlaNet.pdf"/>
    <dc:creator>Wagner, Dorothea</dc:creator>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:creator>Schickenrieder, Wolfram</dc:creator>
    <dc:language>eng</dc:language>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/5854/1/PlaNet.pdf"/>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:00:42Z</dc:date>
  </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
Nein
Begutachtet
Diese Publikation teilen