ﻻ يوجد ملخص باللغة العربية
The Wiener index of a graph is the sum of all pairwise shortest-path distances between its vertices. In this paper we study the novel problem of finding a minimum Wiener connector: given a connected graph $G=(V,E)$ and a set $Qsubseteq V$ of query vertices, find a subgraph of $G$ that connects all query vertices and has minimum Wiener index. We show that The Minimum Wiener Connector admits a polynomial-time (albeit impractical) exact algorithm for the special case where the number of query vertices is bounded. We show that in general the problem is NP-hard, and has no PTAS unless $mathbf{P} = mathbf{NP}$. Our main contribution is a constant-factor approximation algorithm running in time $widetilde{O}(|Q||E|)$. A thorough experimentation on a large variety of real-world graphs confirms that our method returns smaller and denser solutions than other methods, and does so by adding to the query set $Q$ a small number of important vertices (i.e., vertices with high centrality).
We study the problem of finding a minimum homology basis, that is, a shortest set of cycles that generates the $1$-dimensional homology classes with $mathbb{Z}_2$ coefficients in a given simplicial complex $K$. This problem has been extensively studi
A recent breakthrough by Ambainis, Balodis, Iraids, Kokainis, Pr=usis and Vihrovs (SODA19) showed how to construct faster quantum algorithms for the Traveling Salesman Problem and a few other NP-hard problems by combining in a novel way quantum searc
We study the problem of Minimum $k$-Critical Bipartite Graph of order $(n,m)$ - M$k$CBG-$(n,m)$: to find a bipartite $G=(U,V;E)$, with $|U|=n$, $|V|=m$, and $n>m>1$, which is $k$-critical bipartite, and the tuple $(|E|, Delta_U, Delta_V)$, where $Del
The minimum cut problem in an undirected and weighted graph $G$ is to find the minimum total weight of a set of edges whose removal disconnects $G$. We completely characterize the quantum query and time complexity of the minimum cut problem in the ad
A stable cut of a graph is a cut whose weight cannot be increased by changing the side of a single vertex. Equivalently, a cut is stable if all vertices have the (weighted) majority of their neighbors on the other side. In this paper we study Min Sta