Fast Quasi-Threshold Editing

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

BRANDES, Ulrik, Michael HAMANN, Ben STRASSER, Dorothea WAGNER, 2015. Fast Quasi-Threshold Editing

@unpublished{Brandes2015Quasi-31115, title={Fast Quasi-Threshold Editing}, year={2015}, author={Brandes, Ulrik and Hamann, Michael and Strasser, Ben and Wagner, Dorothea} }

<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/rdf/resource/123456789/31115"> <dc:creator>Wagner, Dorothea</dc:creator> <dc:contributor>Wagner, Dorothea</dc:contributor> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/31115"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:contributor>Strasser, Ben</dc:contributor> <dc:creator>Brandes, Ulrik</dc:creator> <dc:contributor>Brandes, Ulrik</dc:contributor> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2015-06-03T09:26:06Z</dcterms:available> <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 edge insertion and deletion. Given a graph it computes a quasi-threshold graph which is close in terms of edit count. This edit problem is NP-hard. We present an extensive experimental study, in which we show that QTM is the first algorithm 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> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:title>Fast Quasi-Threshold Editing</dcterms:title> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:issued>2015</dcterms:issued> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2015-06-03T09:26:06Z</dc:date> <dc:contributor>Hamann, Michael</dc:contributor> <dc:language>eng</dc:language> <dc:creator>Hamann, Michael</dc:creator> <dc:creator>Strasser, Ben</dc:creator> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account