BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Centrality of shortest paths: algorithms and complexity results
DTSTART:20260115T103000
DTEND:20260115T120000
DTSTAMP:20260528T031137Z
UID:488f1f8a0cf6739d0f16d90e49aa2ee5d72fdb746e289e8b54b23e0a
CATEGORIES:Conferences - Seminars
DESCRIPTION:Professor Dmytro MATSYPURA - University of Sydney Business Sc
 hool\nAbstract: The centrality of a node is often used to measure its impo
 rtance to the structure of a network. Some centrality measures can be exte
 nded to measure the importance of a path. In this paper\, we consider the 
 problem of finding the most central shortest path. We show that the comput
 ational complexity of this problem depends on the measure of centrality us
 ed and\, in the case of degree centrality\, whether the network is weighte
 d or not. We develop a polynomial algorithm for the most degree-central sh
 ortest path problem with the worst-case running time of $O(|E||V|^2\\Delta
 (G))$\, where $|V|$ is the number of vertices\, $|E|$ is the number of edg
 es\, and $\\Delta(G)$ is the maximum degree of the graph. In addition\, we
  show that the same problem is NP-hard on a weighted graph. Furthermore\, 
 we show that the problem of finding the most betweenness-central shortest 
 path is solvable in polynomial time\, while finding the most closeness-cen
 tral shortest path is NP-hard\, regardless of whether the graph is weighte
 d or not. We also develop an algorithm for finding the most betweenness-ce
 ntral shortest path with a running time of $O(|E|^2|V|^2)$ on unweighted g
 raphs and $O(|E|^2|V|^2 + |V|^2\\log(|V|))$ on graphs with positively weig
 hted edges. To conclude our paper\, we conduct a numerical study of our al
 gorithms on synthetic and real-world networks and compare our results to t
 he existing literature.\n\nShort bio: Dmytro Matsypura is an Associate Pro
 fessor in the Discipline of Business Analytics at the University of Sydney
  Business School. His current research focus is on applications of convex 
 and combinatorial optimisation in forecasting\, graph theory\, finance\, t
 ransportation\, and ecology.\n\nDr Matsypura received a bachelor's degree 
 in Business Administration\, with honours\, in 1998\, an MS degree in Info
 rmation Systems\, with honours\, in 2000 from Kyiv Polytechnic Institute\,
  and a Ph.D. degree in Management Science from the University of Massachus
 etts Amherst in 2006. In 2007\, he joined the Discipline of Business Analy
 tics at the University of Sydney.\n 
LOCATION:ODY 4 03 https://plan.epfl.ch/?room==ODY%204%2003 https://epfl.zo
 om.us/j/62388786623
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR