KOPS - The Institutional Repository of the University of Konstanz
# Combinatorial Network Abstraction by Trees and Distances

Type of Publication: | Contribution to a conference |

Publication status: | Published |

Author: | Eckhardt, Stefan; Kosub, Sven; Maaß, Moritz G.; Täubig, Hanjo; Wernicke, Sebastian |

Year of publication: | 2005 |

Conference: | International Symposium on Algorithms and Computation : ISAAC 2005, Dec 19, 2005 - Dec 21, 2005, Sanya, China |

Published in: | Algorithms and Computation : 16th International Symposium, ISAAC 2005, Proceedings / Deng, Xiaotie; Du, Ding-Zhu (ed.). - Berlin : Springer, 2005. - (Lecture Notes in Computer Science ; 3827). - pp. 1100-1109. - ISSN 0302-9743. - eISSN 1611-3349. - ISBN 978-3-540-30935-2 |

DOI (citable link): | https://dx.doi.org/10.1007/11602613_109 |

Summary: |
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
_{∞} 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. |

Subject (DDC): | 004 Computer Science |

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} }