Minimum Number of Palettes in Edge Colorings

A proper edge-coloring of a graph defines at each vertex the set of colors of its incident edges. This set is called the palette of the vertex. In this paper we are interested in the minimum number of palettes taken over all possible proper colorings of a graph.     

Scheduling Problems and Mixed Graph Colorings

Some scheduling problems induce a mixed graph coloring, i.e., an assignment of positive integers (colors) to vertices of a mixed graph such that, if two vertices are joined by an edge, then their colors have to be different, and if two vertices are joined by an arc, then the color of the startvertex has to be not greater than the color of the endvertex. We discuss some algorithms for coloring the vertices of a mixed graph with a small number t of colors and present computational results for calculating the chromatic number, i.e., the minimal possible value of such a t . We also study the chromatic polynomial of a mixed graph which may be used for calculating the number of feasible schedules.     

Total Colorings of Graphs with Minimum Sum of Colors

The total chromatic sum of a graph is the minimum sum of colors (natural numbers) taken over all proper colorings of vertices and edges of a graph. We construct infinite families of graphs for which the minimum number of colors to achieve the total chromatic sum is larger than the total chromatic number.     

Extremal H‐Colorings of Graphs with Fixed Minimum Degree

For graphs G and H, a homomorphism from G to H, or H‐coloring of G, is a map from the vertices of G to the vertices of H that preserves adjacency. When H is composed of an edge with one looped endvertex, an H‐coloring of G corresponds to an independent set in G. Galvin showed that, for sufficiently large n, the complete bipartite graph is the n‐vertex graph with minimum degree δ that has the largest number of independent sets. In this article, we begin the project of generalizing this result to arbitrary H. Writing for the number of H‐colorings of G, we show that for fixed H and or , for any n‐vertex G with minimum degree δ (for sufficiently large n). We also provide examples of H for which the maximum is achieved by and other H for which the maximum is achieved by . For (and sufficiently large n), we provide an infinite family of H for which for any n‐vertex G with minimum degree δ. The results generalize to weighted H‐colorings.     

Maximizing H‐Colorings of Connected Graphs with Fixed Minimum Degree

For graphs G and H , an H‐coloring of G is a map from the vertices of G to the vertices of H that preserves edge adjacency. We consider the following extremal enumerative question: for a given H , which connected n‐vertex graph with minimum degree δ maximizes the number of H‐colorings? We show that for nonregular H and sufficiently large n , the complete bipartite graph is the unique maximizer. As a corollary, for nonregular H and sufficiently large n the graph is the unique k‐connected graph that maximizes the number of H‐colorings among all k‐connected graphs. Finally, we show that this conclusion does not hold for all regular H by exhibiting a connected n‐vertex graph with minimum degree δ that has more ‐colorings (for sufficiently large q and n ) than .     

Minimum Cost Compromise Mixed Allocation

When more than one (say p) characteristics in multivariate stratified population are defined on each unit of the population, the individual optimum allocations may differ widely and can not be used practically. Moreover, there may be a situation such that no standard allocation is advisable to all the strata, for one reason or another. In such a situation, Clark and Steel (J R Stat Soc, Ser D Stat 49(2):197–207, 2000) suggested that different allocations may be used for different groups of strata having some common characteristics for double sampling in stratification. Later on, Ahsan et al. (Aligarh J Stat 25:87–97, 2005) used the same concept in univariate stratified sampling. They minimized the variance of the stratified sample mean for a fixed cost to obtain an allocation and called this allocation “mixed allocation”. In the present paper, a “compromise mixed allocation” is worked out for the fixed precisions of the estimates of the p-population means of a multivariate stratified population. A numerical example is also presented.     

无容量限制的最小费用流问题

本文研究了无容量限制的带固定费用和可变费用的单物资和二物资的最小费用流问题,并分别给出了多项式算法.最后应用该算法,计算了一个二物资的最小费用流问题的实例.     

Minimum Cost Allocation of Tenders

In a big organization like the Australian Post Office, where large sums of money are spent to purchase a very large number of items every financial year, the problem is that of allocating the orders of the different items to the competing tenderers at a minimum cost. We have dealt with this in two sections; one is devoted to quantity discounts, the other to order value discounts. We have shown the mathematical formulation using integer and mixed integer linear programming, the mathematical programming systems used, the benefits gained and costs incurred, and the effects of the implementation of minimum cost allocation techniques on the organizational structure of some sections of the A.P.O. We have also shown that these techniques could be used to analyse the relative economic efficiencies of the competing tenderers with the objective of formulating a suitable economic purchasing policy for the organization concerned.     

Feasible Graphs and Colorings

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring.     

Colorings and orientations of graphs

Bounds for the chromatic number and for some related parameters of a graph are obtained by applying algebraic techniques. In particular, the following result is proved: IfG is a directed graph with maximum outdegreed, and if the number of Eulerian subgraphs ofG with an even number of edges differs from the number of Eulerian subgraphs with an odd number of edges then for any assignment of a setS(v) ofd+1 colors for each vertexv ofG there is a legal vertex-coloring ofG assigning to each vertexv a color fromS(v).Research supported in part by a United States-Israel BSF Grant and by a Bergmann Memorial Grant.     

Minimum Cost Homomorphism Dichotomy for Oriented Cycles

For digraphs D and H, a mapping f : V(D) → V(H) is a homomorphism of D to H if uv ∈ A(D) implies f(u) f(v) ∈ A(H). If, moreover, each vertex u ∈ V(D) is associated with costs c _i (u), i ∈ V(H), then the cost of the homomorphism f is ∑ _{u ∈V(D)} c _f(u)(u). For each fixed digraph H, we have the minimum cost homomorphism problem for H (abbreviated MinHOM(H)). The problem is to decide, for an input graph D with costs c _i (u), u ∈ V(D), i ∈ V(H), whether there exists a homomorphism of D to H and, if one exists, to find one of minimum cost. We obtain a dichotomy classification for the time complexity of MinHOM(H) when H is an oriented cycle. We conjecture a dichotomy classification for all digraphs with possible loops.     

最小费用流问题的一种改进算法

本用顶点表和弧表描述和存储最小费用流的参数，借助SQL语言的优点提出了一种求解最小费用流的简便算法。中提出了前沿节点和含潜弧的概念，并利用这些概念减少了最短路算法的迭代次数和每次迭代的计算量。最后给出了一个算例。     

Triple Brackets and Lax Morphism Categories

Various aspects of the traditional homotopy theory of topological spaces may be developed in an arbitrary 2-category C with zeros. In particular certain secondary composition operations called box brackets recently have been defined for C; these are similar to, but extend, the familiar Toda brackets in the topological case. In this paper we introduce further the notion of a suspension functor in C and explore the ramifications of relativizing the theory in terms of the associated lax morphism category of C, denoted mC. Four operations associated to a 3-box diagram are introduced and relations among them are clarified. The results and insights obtained, while by nature somewhat technical, yield effective and efficient techniques for computing many operations of Toda bracket type. We illustrate by recording some computations from the homotopy groups of spheres. Also the properties of a new operation, the 2-sided matrix Toda bracket, are explored.     

Minimum Cost Maintenance in Heavy Haul Rail Track

This paper describes two complementary studies concerning the maintenance and replacement of heavy haul railway track. Minimum cost policies are derived using decision networks in one case and a group replacement model in the other. The results indicate relatively large cost savings on current practice.     

Lower Bounds in Minimum Rank Problems

The minimum rank of a graph is the smallest possible rank among all real symmetric matrices with the given graph. The minimum semidefinite rank of a graph is the minimum rank among Hermitian positive semidefinite matrices with the given graph. We explore connections between OS-sets and a lower bound for minimum rank related to zero forcing sets as well as exhibit graphs for which the difference between the minimum semidefinite rank and these lower bounds can be arbitrarily large.     

Efficient Parallel Algorithms for the Minimum Cost Flow Problem

In this paper, we propose efficient parallel implementations of the auction/sequential shortest path and the -relaxation algorithms for solving the linear minimum cost flow problem. In the parallel auction algorithm, several augmenting paths can be found simultaneously, each of them starting from a different node with positive surplus. Convergence results of an asynchronous version of the algorithm are also given. For the -relaxation method, there exist already parallel versions implemented on CM-5 and CM-2; our implementation is the first on a shared memory multiprocessor. We have obtained significant speedup values for the algorithms considered; it turns out that our implementations are effective and efficient.     

分配网络的一个最小费用流算法

分配网络流广泛应用于解决水源、电力的调度及工厂的产品运输、分配、合成等问题.本文提出一个分配网络流的最小费用流算法.     

基于线性规划的炼钢装炉最小成本控制

基于线性规划方法研究了炼钢装炉最小成本控制问题.建立了炼钢装炉数学模型,给出了单纯形法的算法设计.这种算法可以大大降低成本,适合在工程中使用.最后用数值例子对所得结果加以验证,说明了文中结果的正确性.     

Inessential Combinations and Colorings of Models

We define the operations of an inessential combination and an almost inessential combination of models and theories. We establish basedness for an (almost) inessential combination of theories. We also establish that the properties of smallness and -stability are preserved upon passing to (almost) inessential combinations of theories. We define the notions of coloring of a model, colored model, and colored theory, and transfer the assertions about combinations to the case of colorings. We characterize the inessential colorings of a polygonometry.