Search

Given a graph G=( V, E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k≥3 but well-known to be polynomial-time solvable for k=2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2 l kT( n, m)) time and Vertex Multiterminal Cut can be solved in O( k l T( n, m)) time, where T( n, m)= O(min ( n2/3, m1/2) m) is the running time of finding a minimum ( s, t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415 l T( n, m)) time, and Vertex {3,4,5,6}-Terminal Cuts can be solved in O(2.059 l T( n, m)), O(2.772 l T( n, m)), O(3.349 l T( n, m)) and O(3.857 l T( n, m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: $O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m))$ -time algorithm for Edge Multicut and O((2 k) k+ l/2 T( n, m))-time algorithm for Vertex Multicut. [ABSTRACT FROM AUTHOR]

This paper investigates the power of local computations on graphs, by considering a classical problem in distributed algorithms, the recognition problem. Formally, we want to compute some topological information on a network of processes, possibly using additional knowledge about the structure of the underlying graph. We propose the notion of recognition with structural knowledge by means of local computations. Then we characterize the graph classes that are recognizable with or without structural knowledge. The characterizations use graph coverings and a distributed enumeration algorithm proposed by A. Mazurkiewicz. Several applications are presented, in particular concerning minor-closed classes of graphs. [ABSTRACT FROM AUTHOR]

This paper is dedicated to location problems on graphs. We propose a linear time algorithm for the 1-median problem on wheel graphs. Moreover, some general results for the 1-median problem are summarized and parametric median problems are investigated. These results lead to a solution method for the 2-median problem on cactus graphs, i.e., on graphs where no two cycles have more than one vertex in common. The time complexity of this algorithm is $$\mathcal O(n^2)$$ , where n is the number of vertices of the graph. [ABSTRACT FROM AUTHOR]

In this paper, we give a realization of crystal bases of the fundamental representations over Uq(Cn(1)) in terms of Young diagrams k introduced by Premat. Further, we give a generalized Lascoux–Leclerc–Thibon algorithm for computing the global bases. [ABSTRACT FROM AUTHOR]

In this paper, we give a realization of crystal bases of the fundamental representations over Uq(Cn(1)) in terms of Young diagrams k introduced by Premat. Further, we give a generalized Lascoux–Leclerc–Thibon algorithm for computing the global bases. [ABSTRACT FROM AUTHOR]