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, 2005. Combinatorial Network Abstraction by Trees and Distances. International Symposium on Algorithms and Computation : ISAAC 2005. Sanya, China, Dec 19, 2005 - Dec 21, 2005. In: DENG, Xiaotie, ed., Ding-Zhu DU, ed.. Algorithms and Computation : 16th International Symposium, ISAAC 2005, Proceedings. Berlin:Springer, pp. 1100-1109. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-540-30935-2. Available under: doi: 10.1007/11602613_109

@inproceedings{Eckhardt2005Combi-44985, title={Combinatorial Network Abstraction by Trees and Distances}, year={2005}, doi={10.1007/11602613_109}, number={3827}, isbn={978-3-540-30935-2}, issn={0302-9743}, address={Berlin}, publisher={Springer}, series={Lecture Notes in Computer Science}, booktitle={Algorithms and Computation : 16th International Symposium, ISAAC 2005, Proceedings}, pages={1100--1109}, editor={Deng, Xiaotie and Du, Ding-Zhu}, author={Eckhardt, Stefan and Kosub, Sven and Maaß, Moritz G. and Täubig, Hanjo and Wernicke, Sebastian} }

2019-02-12T11:55:47Z Täubig, Hanjo Maaß, Moritz G. Eckhardt, Stefan Combinatorial Network Abstraction by Trees and Distances Täubig, Hanjo Eckhardt, Stefan This work draws attention to combinatorial network abstraction problems which are specified by a class P of pattern graphs and a real-valued similarity measure ϱ based on certain graph properties. For fixed P and ϱ, the optimization task on any graph G is to find a subgraph G′ which belongs to P and minimizes ϱ(G,G′). We consider this problem for the natural 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 some standard vector and matrix norms. The complexity analysis shows that all considered variants of the problem are NP-complete, except for the case of distance-minimization with respect to the L  <sub>∞</sub>  norm. We further show that unless P = NP, there exist no polynomial-time constant-factor approximation algorithms for the distance-approximation problems if a subset of edges can be forced into the spanning tree. Kosub, Sven 2005 2019-02-12T11:55:47Z Kosub, Sven Wernicke, Sebastian Wernicke, Sebastian Maaß, Moritz G. eng

This item appears in the following Collection(s)

Search KOPS


My Account