Publikation:

All-Pairs Ancestor Problems in Weighted Dags

Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2007

Autor:innen

Baumgart, Matthias
Eckhardt, Stefan
Griebsch, Jan
Nowak, Johannes

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-540-74450-4_26
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

CHEN, Bo, ed., Mike PATERSON, ed., Guochuan ZHANG, ed.. Combinatorics, Algorithms, Probabilistic and Experimental Methodologies : Revised Selected Papers. Berlin: Springer, 2007, pp. 282-293. Lecture Notes in Computer Science. 4614. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-74449-8. Available under: doi: 10.1007/978-3-540-74450-4_26

Zusammenfassung

This work studies (lowest) common ancestor problems in (weighted) directed acyclic graphs. We improve previous algorithms for the all-pairs representative LCA problem to O(n 2.575) by using fast rectangular matrix multiplication. We prove a first non-trivial upper bound of O( min {n 2 m, n 3.575 }) for the all-pairs all lowest common ancestors problem. Furthermore, classes of dags are identified for which the problem can be solved considerably faster. Our algorithms scale with the maximal number of LCAs for one pair and—based on the famous Dilworth’s theorem—with the size of a maximum antichain (i.e., width) of the dag. We extend and generalize previous results on computing shortest ancestral distances. It is shown that finding shortest distance common ancestors in weighted dags is not harder than computing all-pairs shortest distances, up to a polylogarithmic factor. Finally, we present a solution for the general all-pairs shortest distance LCA problem based on computing all-pairs all LCAs.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Transitive Closure, Border Gateway Protocol, Lower Common Ancestor, Maximum Antichain

Konferenz

International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies : ESCAPE 2007, 7. Apr. 2007 - 9. Apr. 2007, Hangzhou, China
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690BAUMGART, Matthias, Stefan ECKHARDT, Jan GRIEBSCH, Sven KOSUB, Johannes NOWAK, 2007. All-Pairs Ancestor Problems in Weighted Dags. International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies : ESCAPE 2007. Hangzhou, China, 7. Apr. 2007 - 9. Apr. 2007. In: CHEN, Bo, ed., Mike PATERSON, ed., Guochuan ZHANG, ed.. Combinatorics, Algorithms, Probabilistic and Experimental Methodologies : Revised Selected Papers. Berlin: Springer, 2007, pp. 282-293. Lecture Notes in Computer Science. 4614. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-74449-8. Available under: doi: 10.1007/978-3-540-74450-4_26
BibTex
@inproceedings{Baumgart2007AllPa-44936,
  year={2007},
  doi={10.1007/978-3-540-74450-4_26},
  title={All-Pairs Ancestor Problems in Weighted Dags},
  number={4614},
  isbn={978-3-540-74449-8},
  issn={0302-9743},
  publisher={Springer},
  address={Berlin},
  series={Lecture Notes in Computer Science},
  booktitle={Combinatorics, Algorithms, Probabilistic and Experimental Methodologies : Revised Selected Papers},
  pages={282--293},
  editor={Chen, Bo and Paterson, Mike and Zhang, Guochuan},
  author={Baumgart, Matthias and Eckhardt, Stefan and Griebsch, Jan and Kosub, Sven and Nowak, 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/44936">
    <dc:creator>Baumgart, Matthias</dc:creator>
    <dc:contributor>Nowak, Johannes</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Griebsch, Jan</dc:contributor>
    <dc:language>eng</dc:language>
    <dcterms:issued>2007</dcterms:issued>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-08T13:19:05Z</dcterms:available>
    <dc:creator>Griebsch, Jan</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Eckhardt, Stefan</dc:creator>
    <dc:contributor>Eckhardt, Stefan</dc:contributor>
    <dc:contributor>Baumgart, Matthias</dc:contributor>
    <dc:contributor>Kosub, Sven</dc:contributor>
    <dc:creator>Nowak, Johannes</dc:creator>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/44936"/>
    <dcterms:title>All-Pairs Ancestor Problems in Weighted Dags</dcterms:title>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2019-02-08T13:19:05Z</dc:date>
    <dcterms:abstract xml:lang="eng">This work studies (lowest) common ancestor problems in (weighted) directed acyclic graphs. We improve previous algorithms for the all-pairs representative LCA problem to O(n &lt;sup&gt;2.575&lt;/sup&gt;) by using fast rectangular matrix multiplication. We prove a first non-trivial upper bound of O( min {n &lt;sup&gt;2&lt;/sup&gt; m, n &lt;sup&gt;3.575&lt;/sup&gt; }) for the all-pairs all lowest common ancestors problem. Furthermore, classes of dags are identified for which the problem can be solved considerably faster. Our algorithms scale with the maximal number of LCAs for one pair and—based on the famous Dilworth’s theorem—with the size of a maximum antichain (i.e., width) of the dag. We extend and generalize previous results on computing shortest ancestral distances. It is shown that finding shortest distance common ancestors in weighted dags is not harder than computing all-pairs shortest distances, up to a polylogarithmic factor. Finally, we present a solution for the general all-pairs shortest distance LCA problem based on computing all-pairs all LCAs.</dcterms:abstract>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Kosub, Sven</dc:creator>
  </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