An Optimal Algorithm to Solve the All-Pairs Shortest Paths Problem on Permutation Graphs

In this paper we present an optimal algorithm to solve the all-pairs shortest path problem on permutation graphs with n vertices and m edges which runs in O(n ²) time. Using this algorithm, the average distance of a permutation graph can also be computed in O(n ²) time.     

Paths on polymatroids

This paper establishes bounds on the length of certain strictly monotone paths, relative to a given linear objective function, on a polymatroid or on the base of a polymatroid. Specialized bounds are given for a strict polymatroid and for a matroid polyhedron. Bounds on the diameter are included.     

Paths through inverse limits

In Bani?, ?repnjak, Merhar and Milutinovi? (2010) [2] the authors proved that if a sequence of graphs of surjective upper semi-continuous set-valued functions fn:X→X² converges to the graph of a continuous single-valued function f:X→X, then the sequence of corresponding inverse limits obtained from fn converges to the inverse limit obtained from f. In this paper a more general result is presented in which surjectivity of fn is not required. The result is also generalized to the case of inverse sequences with non-constant sequences of bonding maps. Finally, these new theorems are applied to inverse limits with tent maps. Among other applications, it is shown that the inverse limits appearing in the Ingram conjecture (with a point added) form an arc.     

Finite Paths are Universal

We prove that any countable (finite or infinite) partially ordered set may be represented by finite oriented paths ordered by the existence of homomorphism between them. This (what we believe a surprising result) solves several open problems. Such path-representations were previously known only for finite and infinite partial orders of dimension 2. Path-representation implies the universality of other classes of graphs (such as connected cubic planar graphs). It also implies that finite partially ordered sets are on-line representable by paths and their homomorphisms. This leads to new on-line dimensions. Mathematics Subject Classifications (2000) 06A06, 06A07, 05E99, 05C99.J. Nešetřil: Supported by a Grant LN00A56 of the Czech Ministry of Education. The first author was partially supported by EU network COMBSTRU at UPC Barcelona.     

������̵Ĺ���ṹ

本文中我们给出了生灭过程的轨道结构,指出轨道结构与构造理论之间的一一对应关系,并且利用Ito游程理论说明构造理论中各个参数的概率含义.     

On Infinitesimally Optimal Paths

The concept of infinitesimal optimality is specified for discrete dynamic extremal problems.     

Finite Paths are Universal

We prove that any countable (finite or infinite) partially ordered set may be represented by finite oriented paths ordered by the existence of homomorphism between them. This (what we believe a surprising result) solves several open problems. Such path-representations were previously known only for finite and infinite partial orders of dimension 2. Path-representation implies the universality of other classes of graphs (such as connected cubic planar graphs). It also implies that finite partially ordered sets are on-line representable by paths and their homomorphisms. This leads to a new on-line dimensions. *Supported by Grants LN00A56 and 1M0021620808 of the Czech Ministry of Education. The first author was partially supported by EU network COMBSTRU at UPC Barcelona.     

Paths of random evolutions

We study the paths of general random evolution processes obtained by piecing together deterministic evolution functions according to the dictates of a regular step process. If the state space is metrizable we show that such processes are strong Markov; and they are even standard under a certain continuity condition on paths. We apply this result to solutions of stochastic delayed differential equations, and we make a connection between our processes and random evolutions associated with classes of semigroups.     

Paths extendable to cycles

Let k be a positive integer, and S a nonempty set of positive integers. Suppose that G is a connected graph containing a path of length k, and that each path P of length k in G is contained in some cycle C(P) of length s ∈ S. We prove that every path of length less than k can be extended to a path of length k in G. This result answers conjectures of Entringer and Reid regarding when certain paths may be extended to cycles.     

Unions of Sets Starshaped via Staircase Paths or via Paths of Bounded Length

Let S be an orthogonal polygon in the plane, S simply connected, and let k=2,3. Set S is a union of k sets starshaped via staircase paths if and only if for every F finite, F bdry S, there is a set G bdry S arbitrarily close to F and points si,1 ik, (depending on G) such that each point of G is clearly visible from some si. An analogous result holds for a union of 2 sets starshaped via -paths when S is a closed simply connected set in the plane. Each result is best possible.     

Minimum Paths in Directed Graphs

This paper considers the problem of finding paths from a fixed node to all other nodes of a directed graph which minimise a function defined on the paths. Under certain assumptions a characterisation of optimal paths is derived. Two algorithms which are generalisations of standard shortest path methods are then given.     

Disjoint Paths in Decomposable Digraphs

The k‐linkage problem is as follows: given a digraph and a collection of k terminal pairs such that all these vertices are distinct; decide whether D has a collection of vertex disjoint paths such that is from to for . A digraph is k‐linked if it has a k‐linkage for every choice of 2k distinct vertices and every choice of k pairs as above. The k‐linkage problem is NP‐complete already for [11] and there exists no function such that every ‐strong digraph has a k‐linkage for every choice of 2k distinct vertices of D [17]. Recently, Chudnovsky et al. [9] gave a polynomial algorithm for the k‐linkage problem for any fixed k in (a generalization of) semicomplete multipartite digraphs. In this article, we use their result as well as the classical polynomial algorithm for the case of acyclic digraphs by Fortune et al. [11] to develop polynomial algorithms for the k‐linkage problem in locally semicomplete digraphs and several classes of decomposable digraphs, including quasi‐transitive digraphs and directed cographs. We also prove that the necessary condition of being ‐strong is also sufficient for round‐decomposable digraphs to be k‐linked, obtaining thus a best possible bound that improves a previous one of . Finally we settle a conjecture from [3] by proving that every 5‐strong locally semicomplete digraph is 2‐linked. This bound is also best possible (already for tournaments) [1].     

Shortest Paths with Shortest Detours

This paper is concerned with a biobjective routing problem, called the shortest path with shortest detour problem, in which the length of a route is minimized as one criterion and, as second, the maximal length of a detour route if the chosen route is blocked is minimized. Furthermore, the relation to robust optimization is pointed out, and we present a new polynomial time algorithm, which computes a minimal complete set of efficient paths for the shortest path with shortest detour problem. Moreover, we show that the number of nondominated points is bounded by the number of arcs in the graph.     

Paths to constrained Nash equilibria

We propose and analyze a primal-dual, infinitesimal method for locating Nash equilibria of constrained, non-cooperative games. The main object is a family of nonstandard Lagrangian functions, one for each player. With respect to these functions the algorithm yields separately, in differential form, directions of steepest-descent in all decision variables and steepest-ascent in all multipliers. For convergence we need marginal costs to be monotone and constraints to be convex inequalities. The method is largely decomposed and amenable for parallel computing. Other noteworthy features are: non-smooth data can be accommodated; no projection or optimization is needed as subroutines; multipliers converge monotonically upward; and, finally, the implementation amounts, in essence, only to numerical integration.     

Paths and edge-connectivity in graphs

Mader proved that for every k-edge-connected graph G (k ≥ 4), there exists a path joining two given vertices such that the subgraph obtained from G by deleting the edges of the path is (k - 2)-edge-connected. A generalization of this and a sufficient condition for existance of 3, 4, or 5 terminus k edge-disjoint paths in graphs are given.     

Minimum Degree and Dominating Paths

A dominating path in a graph is a path P such that every vertex outside P has a neighbor on P. A result of Broersma from 1988 implies that if G is an n‐vertex k‐connected graph and , then G contains a dominating path. We prove the following results. The lengths of dominating paths include all values from the shortest up to at least . For , where a is a constant greater than 1/3, the minimum length of a dominating path is at most logarithmic in n when n is sufficiently large (the base of the logarithm depends on a). The preceding results are sharp. For constant s and , an s‐vertex dominating path is guaranteed by when n is sufficiently large, but (where ) does not even guarantee a dominating set of size s. We also obtain minimum‐degree conditions for the existence of a spanning tree obtained from a dominating path by giving the same number of leaf neighbors to each vertex.