Properly colored paths and cycles

In an edge-colored graph, let d^c(v) be the number of colors on the edges incident to v and let δ^c(G) be the minimum d^c(v) over all vertices v∈G. In this work, we consider sharp conditions on δ^c(G) which imply the existence of properly edge-colored paths and cycles, meaning no two consecutive edges have the same color.     

Kernels by monochromatic paths in digraphs with covering number 2

We call the digraph D an k-colored digraph if the arcs of D are colored with k colors. A subdigraph H of D is called monochromatic if all of its arcs are colored alike. A set N⊆V(D) is said to be a kernel by monochromatic paths if it satisfies the following two conditions: (i) for every pair of different vertices u,v∈N, there is no monochromatic directed path between them, and (ii) for every vertex x∈(V(D)?N), there is a vertex y∈N such that there is an xy-monochromatic directed path. In this paper, we prove that if D is an k-colored digraph that can be partitioned into two vertex-disjoint transitive tournaments such that every directed cycle of length 3,4 or 5 is monochromatic, then D has a kernel by monochromatic paths. This result gives a positive answer (for this family of digraphs) of the following question, which has motivated many results in monochromatic kernel theory: Is there a natural numberlsuch that if a digraphDisk-colored so that every directed cycle of length at mostlis monochromatic, thenDhas a kernel by monochromatic paths?     

A priori estimates for rough PDEs with application to rough conservation laws

We introduce a general weak formulation for PDEs driven by rough paths, as well as a new strategy to prove well-posedness. Our procedure is based on a combination of fundamental a priori estimates with (rough) Gronwall-type arguments. In particular this approach does not rely on any sort of transformation formula (flow transformation, Feynman–Kac representation formula etc.) and is therefore rather flexible. As an application, we study conservation laws driven by rough paths establishing well–posedness for the corresponding kinetic formulation.     

On the cardinality of the Pareto set in bicriteria shortest path problems

Computing shortest paths with two or more conflicting optimization criteria is a fundamental problem in transportation and logistics. We study the problem of finding all Pareto-optimal solutions for the multi-criteria single-source shortest-path problem with nonnegative edge lengths. The standard approaches are generalizations of label-setting (Dijkstra) and label-correcting algorithms, in which the distance labels are multi-dimensional and more than one distance label is maintained for each node. The crucial parameter for the run time and space consumption is the total number of Pareto optima. In general, this value can be exponentially large in the input size. However, in various practical applications one can observe that the input data has certain characteristics, which may lead to a much smaller number—small enough to make the problem efficiently tractable from a practical viewpoint. For typical characteristics which occur in various applications we study in this paper whether we can bound the size of the Pareto set to a polynomial size or not. These characteristics are also evaluated (1) on a concrete application scenario (computing the set of best train connections in view of travel time, fare, and number of train changes) and (2) on a simplified randomized model. It will turn out that the number of Pareto optima on each visited node is restricted by a small constant in our concrete application, and that the size of the Pareto set is much smaller than our worst case bounds in the randomized model. A preliminary short version of this paper appeared in the Proceedings of the 5th Workshop on Algorithm Engineering (WAE 2001), LNCS 2141, Springer Verlag, pp. 185–197 (2001) under the title “Pareto shortest paths is often feasible in practice.”     

THE MAXIMUM NUMBER OF INTERSECTIONS BETWEEN TWO PLANE RECTANGULAR PATHS

We show that the maximum number of intersections between two plane rectangular paths with lengths m and n: 2 ≤ m ≤ n, is 4n 2, if m=4 and n≡1(mod 3); and it is mn 1 otherwise.     

Local Convexity on Smooth Manifolds

Some properties of the spaces of paths are studied in order to define and characterize the local convexity of sets belonging to smooth manifolds and the local convexity of functions defined on local convex sets of smooth manifolds. This paper is dedicated to the memory of Guido Stampacchia. This research was supported in part by the Hungarian Scientific Research Fund, Grants OTKA-T043276 and OTKA-T043241, and by CNR, Rome, Italy.     

On the complexity of the planar directed edge-disjoint paths problem

The edge-disjoint paths problem and many special cases of it are known to be NP-complete. We present a new NP-completeness result for a special case of the problem, namely the directed edge-disjoint paths problem restricted to planar supply graphs and demand graphs consisting of two sets of parallel edges.     

Walking an unknown street with bounded detour

A polygon with two distinguished vertices, s and g, is called a street if the two boundary chains from s to g are mutually weakly visible. For a mobile robot with on-board vision system we describe a strategy for finding a short path from s to g in a street not known in advance, and prove that the length of the path created does not exceed 1 + π times the length of the shortest path from s to g. Experiments suggest that our strategy is much better than this, as no ratio bigger than 1.8 has yet been observed. This is complemented by a lower bound of 1.41 for the relative detour each strategy can be forced to generate.     

On the length of simplex paths: The assignment case

This paper reports on an experimental study of the distribution of the length of simplex paths for the Optimal Assignment Problem. We study the distribution of the pivot counts for a version of the simplex method that with essentially equal probabilities introduces any variable with negative reduced cost into the basis. In this situation the distribution of the pivot counts turns out to be normally distributed and independent of the actual cost coefficients, provided these are sufficiently spread out. Further, the mean and standard deviation grow only moderately with the size of the problem, namely asd ^1.8, andd ^1.5 respectively for ad×d problem, implying in particular that the pivot counts concentrate around the mean with growingd. The usual simplex method on the other hand gives a growth ofd ^1.6. Hence a large part of the favourable polynomial growth experienced on practical problems may be attributed to the fact that the simplex paths are rather short on the average, at least for assignment problems.