A Krasnosel’skii-type result for planar sets starshaped via orthogonally convex paths

A Krasnosel’skii-type theorem for compact sets that are starshaped via staircase paths may be extended to compact sets that are starshaped via orthogonally convex paths: Let S be a nonempty compact planar set having connected complement. If every two points of S are visible via orthogonally convex paths from a common point of S, then S is starshaped via orthogonally convex paths. Moreover, the associated kernel Ker S has the expected property that every two of its points are joined in Ker S by an orthogonally convex path. If S is an arbitrary nonempty planar set that is starshaped via orthogonally convex paths, then for each component C of Ker S, every two of points of C are joined in C by an orthogonally convex path. Communicated by Imre Bárány     

Decomposing Graphs into Long Paths

It is known that the edge set of a 2-edge-connected 3-regular graph can be decomposed into paths of length 3. W. Li asked whether the edge set of every 2-edge-connected graph can be decomposed into paths of length at least 3. The graphs C ₃, C ₄, C ₅, and K ₄−e have no such decompositions. We construct an infinite sequence {F _i } _i=0 ^∞ of nondecomposable graphs. On the other hand, we prove that every other 2-edge-connected graph has a desired decomposition. This revised version was published online in June 2006 with corrections to the Cover Date.     

Path decompositions of multigraphs

Let G be a loopless finite multigraph. For each vertex x of G, denote its degree and multiplicity by d(x) and μ(x) respectively. Define Ø(x) = the least even integer ≥ μ(x), if d(x) is even, the least odd integer ≥ μ(x), if d(x) is odd. In this paper it is shown that every multigraph G admits a faithful path decomposition—a partition P of the edges of G into simple paths such that every vertex x of G is an end of exactly Ø(x) paths in P. This result generalizes Lovász's path decomposition theorem, Li's perfect path double cover theorem (conjectured by Bondy), and a result of Fan concerning path covers of weighted graphs. It also implies an upper bound on the number of paths in a minimum path decomposition of a multigraph, which motivates a generalization of Gallai's path decomposition conjecture. © 1995 John Wiley & Sons, Inc.     

Paths and tableaux descriptions of Jacobi-Trudi determinant associated with quantum affine algebra of type <Emphasis Type="Italic">D</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

We study the Jacobi-Trudi-type determinant which is conjectured to be the q-character of a certain, in many cases irreducible, finite-dimensional representation of the quantum affine algebra of type D _n . Unlike the A _n and B _n cases, a simple application of the Gessel-Viennot path method does not yield an expression of the determinant by a positive sum over a set of tuples of paths. However, applying an additional involution and a deformation of paths, we obtain an expression by a positive sum over a set of tuples of paths, which is naturally translated into the one over a set of tableaux on a skew diagram.     

On tree‐decompositions of one‐ended graphs

A graph is one‐ended if it contains a ray (a one way infinite path) and whenever we remove a finite number of vertices from the graph then what remains has only one component which contains rays. A vertex v dominates a ray in the end if there are infinitely many paths connecting v to the ray such that any two of these paths have only the vertex v in common. We prove that if a one‐ended graph contains no ray which is dominated by a vertex and no infinite family of pairwise disjoint rays, then it has a tree‐decomposition such that the decomposition tree is one‐ended and the tree‐decomposition is invariant under the group of automorphisms. This can be applied to prove a conjecture of Halin from 2000 that the automorphism group of such a graph cannot be countably infinite and solves a recent problem of Boutin and Imrich. Furthermore, it implies that every transitive one‐ended graph contains an infinite family of pairwise disjoint rays.     

Path realization of crystal B(��)

A class of piecewise linear paths, as a generalization of Littelmann’s paths, are introduced, and some operators, acting on the above paths with fixed parametrization, are defined. These operators induce the ordinary Littelmann’s root operators’ action on the equi-alence classes of paths. With these induced operators, an explicit realization of B(∞) is given in terms of equivalence classes of paths, where B(∞) is the crystal base of the negative part of a quantum group U _q (g). Furthermore, we conjecture that there is a complete set of representatives for the above model by fixing a parametrization, and we prove the case when g is of finite type.     

Constructing disjoint paths on expander graphs

In a typical parallel or distributed computation model processors are connected by a spars interconnection network. To establish open-line communication between pairs of processors that wish to communicate interactively, a set of disjoint paths has to be constructed on the network. Since communication needs vary in time, paths have to be dynamically constructed and destroyed.We study the complexity of constructing disjoint paths between given pairs of vertices on expander interconnection graphs. These graphs have been shown before to possess desirable properties for other communication tasks.We present a sufficient condition for the existence ofKn ^Q edge-disjoint paths connecting any set ofK pairs of vertices on an expander graph, wheren is the number of vertices and<1 is some constant. We then show that the computational problem of constructing these paths lies in the classes Deterministic-P and Random-P C.Furthermore, we show that the set of paths can be constructed in probabilistic polylog time in the parallel-distributed model of computation, in which then participating processors reside in the nodes of the communication graph and all communication is done through edges of the graph. Thus, the disjoint paths are constructed in the very computation model that uses them.Finally, we show how to apply variants of our parallel algorithms to find sets ofvertex-disjoint paths when certain conditions are satisfied.Supported in part by a Weizmann fellowship and by contract ONR N00014-85-C-0731.     

Regular path decompositions of odd regular graphs

Kotzig asked in 1979 what are necessary and sufficient conditions for a d‐regular simple graph to admit a decomposition into paths of length d for odd d>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable to a decomposition of the graph into paths of length 3 where the middle edges of the paths coincide with the 1‐factor. We conjecture that existence of a 1‐factor is indeed a sufficient condition for Kotzig's problem. For general odd regular graphs, most 1‐factors appear to be extendable and we show that for the family of simple 5‐regular graphs with no cycles of length 4, all 1‐factors are extendable. However, for d>3 we found infinite families of d‐regular simple graphs with non‐extendable 1‐factors. Few authors have studied the decompositions of general regular graphs. We present examples and open problems; in particular, we conjecture that in planar 5‐regular graphs all 1‐factors are extendable. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 114–128, 2010     

Preemptive Scheduling of Equal-Length Jobs in Polynomial Time

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.     

The Distribution of F st for the Island Model in the Large Population,Weak Mutation Limit

Populations are often divided into subpopulations. Biologists use the statistic F _st to perform hypothesis tests for the existence of population subdivision and to estimate migration rates between different subpopulations. The distribution of F _st is not known. In this article, we use coalescent theory methods to find the limiting distribution of F _st in the large population, weak mutation limit under the island model of migration. Our analysis uses the scattering-collection decomposition of the island model coalescent introduced by Wakeley.     

Simple bounds and greedy algorithms for decomposing a flow into a minimal set of paths

Given arbitrary source and target nodes s, t and an s–t-flow defined by its flow-values on each arc of a network, we consider the problem of finding a decomposition of this flow with a minimal number of s–t-paths. This problem is issued from the engineering of telecommunications networks for which the task of implementing a routing solution consists in integrating a set of end-to-end paths. We show that this problem is NP-hard in the strong sense and give some properties of an optimal solution. We then propose upper and lower bounds for the number of paths in an optimal solution. Finally we develop two heuristics based on the properties of a special set of solutions called saturating solutions.     

A Structure Theorem for Strong Immersions

A graph H is strongly immersed in G if H is obtained from G by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of H are mapped to distinct vertices of G (branch vertices) and edges of H are mapped to pairwise edge‐disjoint paths in G, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion. The theorem roughly states that a graph which excludes a fixed graph as a strong immersion has a tree‐like decomposition into pieces glued together on small edge cuts such that each piece of the decomposition has a path‐like linear decomposition isolating the high degree vertices.     

Multiplicative Decompositions and Frequency of Vanishing of Nonnegative Submartingales

In this paper, we establish a multiplicative decomposition formula for nonnegative local martingales and use it to characterize the set of continuous local submartingales Y of the form Y = N + A, where the measure dA is carried by the set of zeros of Y. In particular, we shall see that in the set of all local submartingales with the same martingale part in the multiplicative decomposition, these submartingales are the smallest ones. We also study some integrability questions in the multiplicative decomposition and interpret the notion of saturated sets in the light of our results.      

Simply connected orthogonal polygons as unions of two orthogonally starshaped sets

Let S be a simply connected orthogonal polygon in the plane. The set S is a union of two sets which are starshaped via staircase paths (i.e., orthogonally starshaped) if and only if for every three points of S, at least two of these points see (via staircase paths) a common point of S. Moreover, the simple connectedness condition cannot be deleted.     

Gaussian quasimartingales

Summary Necessary and sufficient conditions in terms of the mean function and covariance are obtained for a separable Gaussian process to have paths of bounded variation, absolutely continuous or continuous singular. If almost all paths are of bounded variation, the L ² expansion of the Gaussian process is shown to converge in the total variation norm. One then obtains a decomposition of the paths of a Gaussian quasimartingale into a martingale and a predictable process of bounded variation paths such that these components are jointly Gaussian; the martingale component is decomposed into two processes, one consisting of (fixed) jumps and the other a continuous path martingale, and the bounded variation component is decomposed into three processes, one consisting of (fixed) jumps, another with absolutely continuous paths and the third with continuous singular paths. All components are jointly Gaussian. Uniqueness of the decompositions is also established.This work was partially supported by the National Science Foundation.     

Counting Dyck Paths by Area and Rank

The set of Dyck paths of length 2n inherits a lattice structure from a bijection with the set of noncrossing partitions with the usual partial order. In this paper, we study the joint distribution of two statistics for Dyck paths: area (the area under the path) and rank (the rank in the lattice). While area for Dyck paths has been studied, pairing it with this rank function seems new, and we get an interesting (q, t)-refinement of the Catalan numbers. We present two decompositions of the corresponding generating function: One refines an identity of Carlitz and Riordan; the other refines the notion of γ-nonnegativity, and is based on a decomposition of the lattice of noncrossing partitions due to Simion and Ullman. Further, Biane’s correspondence and a result of Stump allow us to conclude that the joint distribution of area and rank for Dyck paths equals the joint distribution of length and reflection length for the permutations lying below the n-cycle (12· · ·n) in the absolute order on the symmetric group.     

On Conditional Covering Problem

The conditional covering problem (CCP) aims to locate facilities on a graph, where the vertex set represents both the demand points and the potential facility locations. The problem has a constraint that each vertex can cover only those vertices that lie within its covering radius and no vertex can cover itself. The objective of the problem is to find a set that minimizes the sum of the facility costs required to cover all the demand points. An algorithm for CCP on paths was presented by Horne and Smith (Networks 46(4):177–185, 2005). We show that their algorithm is wrong and further present a correct O(n ³) algorithm for the same. We also propose an O(n ²) algorithm for the CCP on paths when all vertices are assigned unit costs and further extend this algorithm to interval graphs without an increase in time complexity.     

How fast are the particles of super-Brownian motion?

In this paper we investigate fast particles in the range and support ofsuper-Brownian motion in the historical setting. In this setting eachparticle of super-Brownian motion alive at time t is represented by apath w:[0,t]→ℝ ^d and the state of historical super-Brownian motionis a measure on the set of paths. Typical particles have Brownian paths,however in the uncountable collection of particles in the range of asuper-Brownian motion there are some which at exceptional times movefaster than Brownian motion. We determine the maximal speed of allparticles during a given time period E, which turns out to be afunction of the packing dimension of E. A path w in the support ofhistorical super-Brownian motion at time t is called a-fast if . Wecalculate the Hausdorff dimension of the set of a-fast paths in thesupport and the range of historical super-Brownian motion. A valuabletool in the proofs is a uniform dimension formula for the Browniansnake, which reduces dimension problems in the space of stopped paths to dimension problems on the line. Received: 27 January 2000 / Revised version: 28 August 2000 / Published online: 24 July 2001     

All-Pairs Small-Stretch Paths

Let G = (V, E) be a weighted undirected graph. A path between u, v  V is said to be of stretch t if its length is at most t times the distance between u and v in the graph. We consider the problem of finding small-stretch paths between all pairs of vertices in the graph G.It is easy to see that finding paths of stretch less than 2 between all pairs of vertices in an undirected graph with n vertices is at least as hard as the Boolean multiplication of two n × n matrices. We describe three algorithms for finding small-stretch paths between all pairs of vertices in a weighted graph with n vertices and m edges. The first algorithm, STRETCH₂, runs in Õ(n^3/2m^1/2) time and finds stretch 2 paths. The second algorithm, STRETCH_7/3, runs in Õ(n^7/3) time and finds stretch 7/3 paths. Finally, the third algorithm, STRETCH₃, runs in Õ(n²) and finds stretch 3 paths.Our algorithms are simpler, more efficient and more accurate than the previously best algorithms for finding small-stretch paths. Unlike all previous algorithms, our algorithms are not based on the construction of sparse spanners or sparse neighborhood covers.     

Dynamic Multi-level Overlay Graphs for Shortest Paths

Multi-level overlay graphs represent a speed-up technique for shortest paths computation which is based on a hierarchical decomposition of a weighted directed graph G. They have been shown to be experimentally efficient, especially when applied to timetable information. However, no theoretical result on the cost of constructing, maintaining and querying multi-level overlay graphs in a dynamic environment is known. In this paper, we show theoretical properties of multi-level overlay graphs that lead us to the definition of a new data structure for the computation and the maintenance of an overlay graph of G while weight decrease or weight increase operations are performed on G. Our solution is theoretically faster than the recomputation from scratch and allows queries that can be performed more efficiently than running Dijkstra’s shortest paths algorithm on G. This work was partially supported by the Future and Emerging Technologies Unit of EC (IST priority – 6th FP), under contract no. FP6-021235-2 (project ARRIVAL).