Fast Quasi-Threshold Editing

Lade...
Vorschaubild
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2015
Autor:innen
Hamann, Michael
Strasser, Ben
Wagner, Dorothea
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
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
BANSAL, Nikhil, ed. and others. Algorithms - ESA 2015 : 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, proceedings. Berlin [u.a.]: Springer, 2015, pp. 251-262. Lecture Notes in Computer Science. 9294. ISBN 978-3-662-48349-7. Available under: doi: 10.1007/978-3-662-48350-3_22
Zusammenfassung

We introduce Quasi-Threshold Mover (QTM), an algorithm to solve the quasi-threshold (also called trivially perfect) graph editing problem with a minimum number of edge insertions and deletions. Given a graph it computes a quasi-threshold graph which is close in terms of edit count, but not necessarily closest as this edit problem is NP-hard. We present an extensive experimental study, in which we show that QTM performs well in practice and is the first heuristic that is able to scale to large real-world graphs in practice. As a side result we further present a simple linear-time algorithm for the quasi-threshold recognition problem.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
23rd Annual European Symposium, 14. Sept. 2015 - 16. Sept. 2015, Patras, Greece
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690BRANDES, Ulrik, Michael HAMANN, Ben STRASSER, Dorothea WAGNER, 2015. Fast Quasi-Threshold Editing. 23rd Annual European Symposium. Patras, Greece, 14. Sept. 2015 - 16. Sept. 2015. In: BANSAL, Nikhil, ed. and others. Algorithms - ESA 2015 : 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, proceedings. Berlin [u.a.]: Springer, 2015, pp. 251-262. Lecture Notes in Computer Science. 9294. ISBN 978-3-662-48349-7. Available under: doi: 10.1007/978-3-662-48350-3_22
BibTex
@inproceedings{Brandes2015-11-12Quasi-33493,
  year={2015},
  doi={10.1007/978-3-662-48350-3_22},
  title={Fast Quasi-Threshold Editing},
  number={9294},
  isbn={978-3-662-48349-7},
  publisher={Springer},
  address={Berlin [u.a.]},
  series={Lecture Notes in Computer Science},
  booktitle={Algorithms - ESA 2015 : 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, proceedings},
  pages={251--262},
  editor={Bansal, Nikhil},
  author={Brandes, Ulrik and Hamann, Michael and Strasser, Ben and Wagner, Dorothea}
}
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/33493">
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:creator>Brandes, Ulrik</dc:creator>
    <dc:contributor>Wagner, Dorothea</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Hamann, Michael</dc:contributor>
    <dcterms:abstract xml:lang="eng">We introduce Quasi-Threshold Mover (QTM), an algorithm to solve the quasi-threshold (also called trivially perfect) graph editing problem with a minimum number of edge insertions and deletions. Given a graph it computes a quasi-threshold graph which is close in terms of edit count, but not necessarily closest as this edit problem is NP-hard. We present an extensive experimental study, in which we show that QTM performs well in practice and is the first heuristic that is able to scale to large real-world graphs in practice. As a side result we further present a simple linear-time algorithm for the quasi-threshold recognition problem.</dcterms:abstract>
    <dc:creator>Strasser, Ben</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/33493/1/Brandes_0-324735.pdf"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2016-03-30T08:46:33Z</dc:date>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/33493"/>
    <dc:contributor>Strasser, Ben</dc:contributor>
    <dcterms:title>Fast Quasi-Threshold Editing</dcterms:title>
    <dc:creator>Hamann, Michael</dc:creator>
    <dc:contributor>Brandes, Ulrik</dc:contributor>
    <dc:language>eng</dc:language>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/33493/1/Brandes_0-324735.pdf"/>
    <dcterms:issued>2015-11-12</dcterms:issued>
    <dc:creator>Wagner, Dorothea</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2016-03-30T08:46:33Z</dcterms:available>
    <dc:rights>terms-of-use</dc:rights>
  </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