Fast Quasi-Threshold Editing
Fast Quasi-Threshold Editing
Date
2015
Authors
Editors
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
URI (citable link)
DOI (citable link)
International patent number
Link to the license
EU project number
Project
Open Access publication
Collections
Title in another language
Publication type
Contribution to a conference collection
Publication status
Published
Published in
Algorithms - ESA 2015 : 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, proceedings / Bansal, Nikhil et al. (ed.). - Berlin [u.a.] : Springer, 2015. - (Lecture Notes in Computer Science ; 9294). - pp. 251-262. - ISBN 978-3-662-48349-7
Abstract
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.
Summary in another language
Subject (DDC)
004 Computer Science
Keywords
Conference
23rd Annual European Symposium, Sep 14, 2015 - Sep 16, 2015, Patras, Greece
Review
undefined / . - undefined, undefined. - (undefined; undefined)
Cite This
ISO 690
BRANDES, Ulrik, Michael HAMANN, Ben STRASSER, Dorothea WAGNER, 2015. Fast Quasi-Threshold Editing. 23rd Annual European Symposium. Patras, Greece, Sep 14, 2015 - Sep 16, 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, pp. 251-262. ISBN 978-3-662-48349-7. Available under: doi: 10.1007/978-3-662-48350-3_22BibTex
@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>
Internal note
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Examination date of dissertation
Method of financing
Comment on publication
Alliance license
Corresponding Authors der Uni Konstanz vorhanden
International Co-Authors
Bibliography of Konstanz
Yes