Combinatorial network abstraction by trees and distances

Zitieren

Dateien zu dieser Ressource

Dateien Größe Format Anzeige

Zu diesem Dokument gibt es keine Dateien.

ECKHARDT, Stefan, Sven KOSUB, Moritz G. MAASS, Hanjo TÄUBIG, Sebastian WERNICKE, 2008. Combinatorial network abstraction by trees and distances. In: Theoretical Computer Science. 407(1/3), pp. 1-20

@article{Eckhardt2008Combi-3030, title={Combinatorial network abstraction by trees and distances}, year={2008}, doi={10.1016/j.tcs.2008.03.037}, number={1/3}, volume={407}, journal={Theoretical Computer Science}, pages={1--20}, author={Eckhardt, Stefan and Kosub, Sven and Maaß, Moritz G. and Täubig, Hanjo and Wernicke, Sebastian} }

<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:dcterms="http://purl.org/dc/terms/" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/rdf/resource/123456789/3030"> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/3030"/> <dcterms:rights rdf:resource="http://nbn-resolving.org/urn:nbn:de:bsz:352-20140905103416863-3868037-7"/> <dcterms:issued>2008</dcterms:issued> <dcterms:abstract xml:lang="eng">We draw attention to combinatorial network abstraction problems. These are specified by a class P of pattern graphs and a real-valued similarity measure Q that is based on certain graph properties. For a fixed pattern P and similarity measure Q, the optimization task on a given graph G is to find a subgraph G' subset of G which belongs to P and minimizes Q(G, G'). In this work, we consider this problem for the natural and somewhat general case of trees and distance-based similarity measures. In particular, we systematically study spanning trees of graphs that minimize distances, approximate distances, and approximate closeness-centrality with respect to standard vector- and matrix-norms. Complexity analysis within a unifying framework shows that all considered variants of the problem are NP-complete, except for the case of distance-minimization with respect to the norm L-infinity. If a subset of edges can be "forced" into the spanning tree, no polynomial-time constant-factor approximation algorithmexists for the distance-approximation problems unless P = NP.</dcterms:abstract> <dc:contributor>Maaß, Moritz G.</dc:contributor> <dc:contributor>Kosub, Sven</dc:contributor> <dcterms:bibliographicCitation>Publ. in: Theoretical Computer Science, 407 (2008), 1/3, pp. 1-20</dcterms:bibliographicCitation> <dc:contributor>Wernicke, Sebastian</dc:contributor> <dc:creator>Wernicke, Sebastian</dc:creator> <dc:creator>Kosub, Sven</dc:creator> <dc:creator>Eckhardt, Stefan</dc:creator> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-23T10:15:50Z</dcterms:available> <dc:language>eng</dc:language> <dc:contributor>Täubig, Hanjo</dc:contributor> <dc:contributor>Eckhardt, Stefan</dc:contributor> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-23T10:15:50Z</dc:date> <dc:creator>Täubig, Hanjo</dc:creator> <dc:rights>deposit-license</dc:rights> <dc:creator>Maaß, Moritz G.</dc:creator> <dcterms:title>Combinatorial network abstraction by trees and distances</dcterms:title> </rdf:Description> </rdf:RDF>

Das Dokument erscheint in:

KOPS Suche


Stöbern

Mein Benutzerkonto