Combinatorial network abstraction by trees and distances

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

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. Available under: doi: 10.1016/j.tcs.2008.03.037

@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:dcterms="" xmlns:dc="" xmlns:rdf="" xmlns:bibo="" xmlns:dspace="" xmlns:foaf="" xmlns:void="" xmlns:xsd="" > <rdf:Description rdf:about=""> <bibo:uri rdf:resource=""/> <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> <dcterms:issued>2008</dcterms:issued> <dc:contributor>Kosub, Sven</dc:contributor> <dcterms:isPartOf rdf:resource=""/> <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="">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="">2011-03-23T10:15:50Z</dc:date> <dc:creator>Täubig, Hanjo</dc:creator> <dspace:isPartOfCollection rdf:resource=""/> <dc:creator>Maaß, Moritz G.</dc:creator> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dc:rights>terms-of-use</dc:rights> <dcterms:title>Combinatorial network abstraction by trees and distances</dcterms:title> <dcterms:rights rdf:resource=""/> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


My Account