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].     

On Vaporizing Water Flow in Hot Sub-Vertical Rock Fractures

Water injection into unsaturated fractured rock at above-boiling temperatures gives rise to complex fluid flow and heat transfer processes. Examples include water injection into depleted vapor-dominated geothermal reservoirs, and emplacement of heat-generating nuclear wastes in unsaturated fractured rock. We conceptualize fractures as two-dimensional heterogeneous porous media, and use geostatistical techniques to generate synthetic permeability distributions in the fracture plane. Water flow in hot high-angle fractures is simulated numerically, taking into account the combined action of gravity, capillary, and pressure forces, and conductive heat transfer from the wall rocks which gives rise to strong vaporization. In heterogeneous fractures boiling plumes are found to have dendritic shapes, and to be subject to strong lateral flow effects. Fractures with spatially-averaged homogeneous permeabilities tend to give poor approximations for vaporization behavior and liquid migration patterns. Depending on water flow rates, rock temperature, and fracture permeability, liquid water can migrate considerable distances through fractured rock that is at above-boiling temperatures and be only partially vaporized.     

Weight functions for interface cracks in dissimilar anisotropic materials

Bueckner‘s work conjugate integral customarily adopted for linear elastic materials is established for an interface crack in dissimilar anisotropic materials. The difficulties in separating Stroh‘s six complex arguments involved in the integral for the dissimilar materials are overcome and then the explicit function representations of the integral are given and studied in detail. It is found that the pseudo-orthogonal properties of the eigenfunction expansion form (EEF) for a crack presented previously in isotropic elastic cases, in isotopic bimaterial cases, and in orthotropic cases are also valid in the present dissimilar arbitrary anisotropic cases. The relation between Bueckner‘s work conjugate integral and the J-integral in these cases is obtained by introducing a complementary stressdisplacement state. Finally, some useful path-independent integrals and weight functions are proposed for calculating the crack tip parameters such as the stress intensity factors.     

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.     

高温高应变率下异种不锈钢激光焊接件的力学性能

利用改进的SHTB实验设备,对316L和304不锈钢焊接结构的动态力学性能进行了实验.提出了一种适用于焊接结构件的新型的SHTB夹持装置,并在应变率约103 s-1、温度为25～500℃的环境下获得了焊接结构件动态应力-应变曲线.研究表明:随应变率的升高,结构件的屈服强度和抗拉强度随应变率的增大而增大,随温度的升高而降...     

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.