Гибрид двух новых методов, спектральной кластеризации и метод таксономии - применяется для анализа научно-исследовательской деятельности кафедры. Приведенн пример, иллюстрирующий этот метод, который применяется для решения реальных задач.
Cohen et al. developed an O(log n)-approximation algorithm for minimizing the total hub label size (l1 norm). We give O(log n)- approximation algorithms for the problems of minimizing the maximum label (l∞ norm) and minimizing lp and lq norms simultaneously.
A digraph G = (V,E) with a distinguished set T ⊆ V of terminals is called inner Eulerian if for each v ∈ V − T the numbers of arcs entering and leaving v are equal. By a T-path we mean a simple directed path connecting distinct terminals with all intermediate nodes in V −T. This paper concerns the problem of finding a maximum T-path packing, i.e. a maximum collection of arc-disjoint T-paths. A min-max relation for this problem was established by Lomonosov. The capacitated version was studied by Ibaraki, Karzanov, and Nagamochi, who came up with a strongly-polynomial algorithm of complexity O(φ(V,E) ・ log T +V 2E) (hereinafter φ(n,m) denotes the complexity of a max-flow computation in a network with n nodes and m arcs). For unit capacities, the latter algorithm takes O(φ(V,E) ・ log T +V E) time, which is unsatisfactory since a max-flow can be found in o(V E) time. For this case, we present an improved method that runs in O(φ(V,E) ・ log T + E log V ) time. Thus plugging in the max-flow algorithm of Dinic, we reduce the overall complexity from O(V E) to O(min(V 2/3E,E3/2) ・ log T).
We present a new concept of biclique as a tool for preimage attacks, which employs many powerful techniques from differential cryptanalysis of block ciphers and hash functions. The new tool has proved to be widely applicable by inspiring many authors to publish new results of the full versions of AES, KASUMI, IDEA, and Square. In this paper, we show how our concept leads to the first cryptanalysis of the round-reduced Skein hash function, and describe an attack on the SHA-2 hash function with more rounds than before.
An additive spectral method for fuzzy clustering is presented. The method operates on a clustering model which is an extension of the spectral decomposition of a square matrix. The computation proceeds by extracting clusters one by one, which allows us to draw several stoppingrules to the procedure. We experimentally test the performance of our method and show its competitiveness.method and show its competitiveness.
Let G = (V,E) be a digraph with disjoint sets of sources S ⊂ V and sinks T ⊂ V endowed with an S–T flow f : E → Z+. It is a well-known fact that f decomposes into a sum_st(fst) of s–t flows fst between all pairs of sources s ∈ S and sinks t ∈ T . In the usual RAM model, such a decomposition can be found in O(E log V 2 E ) time. The present paper concerns the complexity of this problem in the external memory model (introduced by Aggarwal and Vitter). The internal memory algorithm involves random memory access and thus becomes inefficient. We propose two novel methods. The first one requires O(Sort(E) log V 2 E ) I/Os and the second one takes O(Sort(E) log U) expected I/Os (where U denotes the maximum value of f).