Multi-Faithful Spanning Trees of Infinite Graphs

For an end and a tree T of a graph G we denote respectively by m() and m _T () the maximum numbers of pairwise disjoint rays of G and T belonging to , and we define tm() := min{m _T(): T is a spanning tree of G}. In this paper we give partial answers — affirmative and negative ones — to the general problem of determining if, for a function f mapping every end of G to a cardinal f() such that tm() f() m(), there exists a spanning tree T of G such that m _T () = f() for every end of G.     

一个在置换图中寻找DFS树的最优算法

本是通过在连通置换图中构造辅助树的方法,给出了一个在具有n个顶点的置换图G中寻找深度优先支撑树（简称,DFS树）的最优算法,并证明了该算法的时间复杂性为O(n)。     

Long cycles and spanning subgraphs of locally maximal 1-planar graphs

A graph is 1-planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1-planar. For a 3-connected locally maximal 1-planar graph G, we show the existence of a spanning 3-connected planar subgraph and prove that G is Hamiltonian if G has at most three 3-vertex-cuts, and that G is traceable if G has at most four 3-vertex-cuts. Moreover, infinitely many nontraceable 5-connected 1-planar graphs are presented.     

Intertwining wavelets or multiresolution analysis on graphs through random forests

We propose a new method for performing multiscale analysis of functions defined on the vertices of a finite connected weighted graph. Our approach relies on a random spanning forest to downsample the set of vertices, and on approximate solutions of Markov intertwining relation to provide a subgraph structure and a filter bank leading to a wavelet basis of the set of functions. Our construction involves two parameters q and $q^{\prime }$. The first one controls the mean number of kept vertices in the downsampling, while the second one is a tuning parameter between space localization and frequency localization. We provide an explicit reconstruction formula, bounds on the reconstruction operator norm and on the error in the intertwining relation, and a Jackson-like inequality. These bounds lead to recommend a way to choose the parameters q and $q^{\prime }$. We illustrate the method by numerical experiments.     

A parallel search algorithm for directed acyclic graphs

A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)²) whenO(n ^2.81/logn) processors are used.     

Spanning network games

We study fundamental properties of monotone network enterprises which contain public vertices and have positive and negative costs on edges and vertices. Among the properties studied are the nonemptiness of the core, characterization of nonredundant core constraints, ease of computation of the core and the nucleolus, and cases of decomposition of the core and the nucleolus. Received December 1994/Final version March 1998     

An exact algorithm for the capacitated shortest spanning arborescence

We are given a complete and loop-free digraphG=(V, A), whereV={1,...,n} is the vertex set,A={(i, j) :i, j V} the arc set, andr V is a distinguishedroot vertex. For each arc (i, j) A, letc _ij be the associatedcost, and for each vertexi, letq _i 0 be the associateddemand (withq _r =0). Moreover, a nonnegativebranch capacity, Q, is defined.A Capacitated Shortest Spanning Arborescence rooted at r (CSSA _r ) is a minimum cost partial digraph such that: (i) each vertexj r has exactly one entering arc; (ii) for each vertexj r, a path fromr toj exists; (iii) for each branch leaving vertexr, the total demand of the vertices does not exceed the branch capacity,Q. A variant of theCSSA _r problem (calledD-CSSA _r ) arises when the out-degree of the root vertex is constrained to be equal to a given valueD. These problems are strongly NP-hard, and find practical applications in routing and network design. We describe a new Lagrangian lower bound forCSSA _r andD-CSSA _r problems, strengthened in a cutting plane fashion by iteratively adding violated constraints to the Lagrangian problem. We also present a new lower bound based on projection leading to the solution of min-cost flow problems. The two lower bounds are then combined so as to obtain an overall additive lower bounding procedure. The additive procedure is then imbedded in a branch-and-bound algorithm whose performance is enhanced by means of reduction procedures, dominance criteria, feasibility checks and upper bounding. Computational tests on asymmetric and symmetric instances from the literature, involving up to 200 vertices, are given, showing the effectiveness of the proposed approach.     

Another greedy heuristic for the constrained forest problem

The constrained forest problem seeks a minimum-weight spanning forest in an undirected edge-weighted graph such that each tree spans at least a specified number of vertices. We present a greedy heuristic for this NP-hard problem, whose solutions are at least as good as, and often better than, those produced by the best-known 2-approximate heuristic.     

改进的生成树遗传算法及其在物流配送成本优化中的应用

针对物流配送成本优化问题的特点,建立了数学模型,并对基本的生成树遗传算法进行了改进,同时详细阐述了改进的生成树编码的遗传算法在物流配送成本优化问题中的运用等关键技术.最后根据此算法设计了一个物流配送优化系统,解决了一个物流配送成本优化问题,效果良好.此系统对于中小型物流公司设计最优物流策略和降低物流成本有着很大的应用前景.