---
title: "Efficient Algorithms for Spanning Tree Centrality"
authors:
  - "Takanori Hayashi"
  - "Takuya Akiba"
  - "Yuichi Yoshida"
doi: ""
url: "https://ijcai.org/proceedings/2016/525"
pdf: "https://ijcai.org/proceedings/2016/0525.pdf"
venue: "Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence"
year: 2016
pages: "3733-3738"
track: ""
keywords:
---

# Efficient Algorithms for Spanning Tree Centrality

Takanori Hayashi, Takuya Akiba, Yuichi Yoshida

*Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence*, pages 3733-3738.

## Abstract

In a connected graph, spanning tree centralities of a vertex and an edge measure how crucial they are for the graph to be connected. In this paper, we propose efficient algorithms for estimating spanning tree centralities with theoretical guarantees on their accuracy. We experimentally demonstrate that our methods are orders of magnitude faster than previous methods. Then, we propose a novel centrality notion of a vertex, called aggregated spanning tree centrality, which also considers the number of connected components obtained by removing the vertex. We also give an efficient algorithm for estimating aggregated spanning tree centrality. Finally, we experimentally show that those spanning tree centralities are useful to identify vulnerable edges and vertices in infrastructure networks.