Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Extending reduction techniques for the Steiner tree problem: a combination of alternative-and bound-based approaches

Polzin, T., & Vahdati, S.(2001). Extending reduction techniques for the Steiner tree problem: a combination of alternative-and bound-based approaches (MPI-I-2001-1-007). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-6D16-F Versions-Permalink: https://hdl.handle.net/21.11116/0000-0001-7AC5-8
Genre: Bericht

Dateien

einblenden: Dateien
ausblenden: Dateien
:
MPI-I-2001-1-007.pdf (beliebiger Volltext), 335KB
Öffnen   Speichern
Datei-Permalink:
https://hdl.handle.net/21.11116/0000-0001-7AC6-7
Name:
MPI-I-2001-1-007.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Öffnen
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Polzin, Tobias1, Autor           
Vahdati, Siavash2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: A key ingredient of the most successful algorithms for the Steiner problem are reduction methods, i.e. methods to reduce the size of a given instance while preserving at least one optimal solution (or the ability to efficiently reconstruct one). While classical reduction tests just inspected simple patterns (vertices or edges), recent and more sophisticated tests extend the scope of inspection to more general patterns (like trees). In this paper, we present such an extended reduction test, which generalizes different tests in the literature. We use the new approach of combining alternative- and bound-based methods, which substantially improves the impact of the tests. We also present several algorithmic improvements, especially for the computation of the needed information. The experimental results show a substantial improvement over previous methods using the idea of extension.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2001
 Publikationsstatus: Erschienen
 Seiten: 24 p.
 Ort, Verlag, Ausgabe: Saarbrücken : Max-Planck-Institut für Informatik
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: Reportnr.: MPI-I-2001-1-007
BibTex Citekey: MPI-I-2001-1-007
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Research Report / Max-Planck-Institut für Informatik
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: - Identifikator: -