Flow Decompositions in External Memory
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).
A galaxy is a forest of directed stars. The notion of galaxy can be related to Facility Location problems as well as wavelength assignment problems in optical networks. Amini et al. [Combinatorics, Probability & Computing, 19(2):161–182, 2010.] and Gonçalves et al. [Discrete Applied Mathematics, 160(6):744–754, 2012.] gave bounds on the minimum number of galaxies needed to cover the arcs of a digraph D, called directed star arboricity (dst(D)). They conjectured that those bounds could be improved such that , for and for . In this work, we study the directed star arboricity in two non-trivial digraph classes: k-degenerate digraphs and tournaments.
This book constitutes the refereed proceedings of the 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013, held in Bad Herrenalb (near Karlsruhe), Germany, in June 2013. The 21 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 51 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivial combinatorial properties of such structures and to exploit these properties in order to either achieve superior performance for the corresponding computational problem or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.
A general algorithm for the decomposition of differences between two values of an aggregate demographic measure of age and other dimensions is realized as Excel/VBA. It assumes that the aggregate measure is computed from similar matrices of discrete demographic data for two populations under comparison. The algorithm estimates the effects of replacement for each elementary cell of one matrix by the respective cell of another matrix. The replacement runs from young to old ages.
For the classical backward induction algorithm, the input is an arbitrary n n -person positional game with perfect information modelled by a finite acyclic directed graph (digraph) and the output is a profile (x 1 ,…,x n ) (x1,…,xn) of pure positional strategies that form some special subgame perfect Nash equilibrium (NE). We extend this algorithm to work with digraphs that may have directed cycles. Each digraph admits a unique partition into strongly connected (SC) components, which will be treated as the outcomes of a game. Such games will be called deterministic graphical multistage (DGMS) games. If we merge the outcomes corresponding to all SC components, except terminals, we obtain the so-called deterministic graphical (DG) games, which are frequent in the literature. The outcomes of a DG game are all terminals and one special outcome c c that is assigned to all infinite plays. We modify the backward induction procedure to adapt it for the DG and DGMS games. Yet, we have to pay the price for this extension. The new algorithm always outputs an NE only when n=2 n=2 and, even in this case, the obtained NE may be not subgame perfect. (Although in the zero-sum case it is.) The lack of these two properties is not a fault of the algorithm, just (subgame perfect) NEs in pure positional strategies may fail to exist in the considered game.
The method of the decision of distinction of digraphs problem is offered. The basis of this method is defined on matrix model of complexity, which takes into account the quantitative and qualitative characteristics of digraph fragments. The model for the first time allows to calculate the importance of each digraph fragment of digraph in its total complexity. The results of the decision of problems of distinction and definition of similarity for digraphs are given.
We consider certain spaces of functions on the circle, which naturally appear in harmonic analysis, and superposition operators on these spaces. We study the following question: which functions have the property that each their superposition with a homeomorphism of the circle belongs to a given space? We also study the multidimensional case.
We consider the spaces of functions on the m-dimensional torus, whose Fourier transform is p -summable. We obtain estimates for the norms of the exponential functions deformed by a C1 -smooth phase. The results generalize to the multidimensional case the one-dimensional results obtained by the author earlier in “Quantitative estimates in the Beurling—Helson theorem”, Sbornik: Mathematics, 201:12 (2010), 1811 – 1836.
We consider the spaces of function on the circle whose Fourier transform is p-summable. We obtain estimates for the norms of exponential functions deformed by a C1 -smooth phase.