On Minimum Edge Ranking Spanning Trees

In this paper, we introduce the problem of computing a minimum edge ranking spanning tree (MERST); i.e., find a spanning tree of a given graph G whose edge ranking is minimum. Although the minimum edge ranking of a given tree can be computed in polynomial time, we show that problem MERST is NP-hard. Furthermore, we present an approximation algorithm for MERST, which realizes its worst case performance ratio where n is the number of vertices in G and Δ* is the maximum degree of a spanning tree whose maximum degree is minimum. Although the approximation algorithm is a combination of two existing algorithms for the restricted spanning tree problem and for the minimum edge ranking problem of trees, the analysis is based on novel properties of the edge ranking of trees.     

Revisiting dynamic programming for finding optimal subtrees in trees

In this paper we revisit an existing dynamic programming algorithm for finding optimal subtrees in edge weighted trees. This algorithm was sketched by Maffioli in a technical report in 1991. First, we adapt this algorithm for the application to trees that can have both node and edge weights. Second, we extend the algorithm such that it does not only deliver the values of optimal trees, but also the trees themselves. Finally, we use our extended algorithm for developing heuristics for the k-cardinality tree problem in undirected graphs G with node and edge weights. This NP-hard problem consists of finding in the given graph a tree with exactly k edges such that the sum of the node and the edge weights is minimal. In order to show the usefulness of our heuristics we conduct an extensive computational analysis that concerns most of the existing problem instances. Our results show that with growing problem size the proposed heuristics reach the performance of state-of-the-art metaheuristics. Therefore, this study can be seen as a cautious note on the scaling of metaheuristics.     

Minimum edge ranking spanning trees of split graphs

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split.     

Edge searching weighted graphs

In traditional edge searching one tries to clean all of the edges in a graph employing the least number of searchers. It is assumed that each edge of the graph initially has a weight equal to one. In this paper we modify the problem and introduce the Weighted Edge Searching Problem by considering graphs with arbitrary positive integer weights assigned to its edges. We give bounds on the weighted search number in terms of related graph parameters including pathwidth. We characterize the graphs for which two searchers are sufficient to clear all edges. We show that for every weighted graph the minimum number of searchers needed for a not-necessarily-monotonic weighted edge search strategy is enough for a monotonic weighted edge search strategy, where each edge is cleaned only once. This result proves the NP-completeness of the problem.     

New proofs for Levine’s theorems

Recently, Levine [9] expressed the vertex weighted complexity on spanning trees (with a fixed root) of the directed line graph of a digraph D in terms of the edge weighted complexity on spanning trees (with a fixed root) of D. We present new proofs for two Levine’s Theorems. Furthermore, we express the number of unicycles of the directed line graph of a digraph D in terms of the number of unicycles of D.     

Approximation hardness of min-max tree covers

We prove the first inapproximability bounds to study approximation hardness for a min-max k-tree cover problem and its variants. The problem is to find a set of k trees to cover vertices of a given graph with metric edge weights, so as to minimize the maximum total edge weight of any of the k trees. Our technique can also be applied to improve inapproximability bounds for min-max problems that use other covering objectives, such as stars, paths, and tours.     

Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree

Given an undirected graph with edge weights, we are asked to find an orientation, that is, an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO, and is a restricted variant of the well-known minimum makespan problem. As in previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs, and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tighter thresholds of complexity: We show that MMO is (i) in P for cactus graphs, (ii) weakly NP-hard for outerplanar graphs, and also (iii) strongly NP-hard for graphs which are both planar and bipartite. This implies the NP-hardness for P₄-bipartite, diamond-free or house-free graphs, each of which is a superclass of cactus. We also show (iv) the NP-hardness for series-parallel graphs and multi-outerplanar graphs, and (v) present a pseudo-polynomial time algorithm for graphs with bounded treewidth.     

On finding most uniform spanning trees

We consider the following problem. Given a graph G and a real valued weight for each edge in G, find a spanning tree T of G such that the difference in weight between the most and least weighted edge in T is minimized. We show an O(m log n) algorithm for this problem, where m is the number of edges and n is the number of vertices in G. This algorithm improves the algorithm given by Camerini et al. [1] for the same problem.     

The Proportional Colouring Problem: Optimizing Buffers in Wireless Mesh Networks

In this paper, we consider a new edge colouring problem motivated by wireless mesh networks optimization: the proportional edge colouring problem. Given a graph G with positive weights associated to its edges, we want to find a proper edge colouring which assigns to each edge at least a proportion (given by its weight) of all the colours. If such colouring exists, we want to find one using the minimum number of colours. We proved that deciding if a weighted graph admits a proportional edge colouring is polynomial while determining its proportional edge chromatic number is NP-hard. We also give a lower and an upper bound that can be polynomially computed. We finally characterize some graphs and weighted graphs for which we can determine the proportional edge chromatic number.     

Enumerating spanning trees of graphs with an involution

As the extension of the previous work by Ciucu and the present authors [M. Ciucu, W.G. Yan, F.J. Zhang, The number of spanning trees of plane graphs with reflective symmetry, J. Combin. Theory Ser. A 112 (2005) 105-116], this paper considers the problem of enumeration of spanning trees of weighted graphs with an involution which allows fixed points. We show that if G is a weighted graph with an involution, then the sum of weights of spanning trees of G can be expressed in terms of the product of the sums of weights of spanning trees of two weighted graphs with a smaller size determined by the involution of G. As applications, we enumerate spanning trees of the almost-complete bipartite graph, the almost-complete graph, the Möbius ladder, and the almost-join of two copies of a graph.     

Enhanced negative type for finite metric trees

A finite metric tree is a finite connected graph that has no cycles, endowed with an edge weighted path metric. Finite metric trees are known to have strict 1-negative type. In this paper we introduce a new family of inequalities (1) that encode the best possible quantification of the strictness of the non-trivial 1-negative type inequalities for finite metric trees. These inequalities are sufficiently strong to imply that any given finite metric tree (T,d) must have strict p-negative type for all p in an open interval (1−ζ,1+ζ), where ζ>0 may be chosen so as to depend only upon the unordered distribution of edge weights that determine the path metric d on T. In particular, if the edges of the tree are not weighted, then it follows that ζ depends only upon the number of vertices in the tree.We also give an example of an infinite metric tree that has strict 1-negative type but does not have p-negative type for any p>1. This shows that the maximal p-negative type of a metric space can be strict.     

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

We study complexity and approximation of min weighted node coloring in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove that min weighted node coloring is NP-hard in P₈-free bipartite graphs, but polynomial for P₅-free bipartite graphs. We next focus on approximability in general bipartite graphs and improve earlier approximation results by giving approximation ratios matching inapproximability bounds. We next deal with min weighted edge coloring in bipartite graphs. We show that this problem remains strongly NP-hard, even in the case where the input graph is both cubic and planar. Furthermore, we provide an inapproximability bound of 7/6−ε, for any ε>0 and we give an approximation algorithm with the same ratio. Finally, we show that min weighted node coloring in split graphs can be solved by a polynomial time approximation scheme.     

Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem

The minimum vertex ranking spanning tree problem (MVRST) is to find a spanning tree of G whose vertex ranking is minimum. In this paper, we show that MVRST is NP-hard. To prove this, we polynomially reduce the 3-dimensional matching problem to MVRST. Moreover, we present a (⌈D_s/2⌉+1)/(⌊log₂(D_s+1)⌋+1)-approximation algorithm for MVRST where D_s is the minimum diameter of spanning trees of G.     

Efficient computation of 2-medians in a tree network with positive/negative weights

We consider a variant of the classical two median facility location problem on a tree in which vertices are allowed to have positive or negative weights. This problem was proposed by Burkard et al. in 2000 (R.E. Burkard, E. Çela, H. Dollani, 2-medians in trees with pos/neg-weights, Discrete Appl. Math. 105 (2000) 51-71). who looked at two objectives, finding the total minimum weighted distance (MWD) and the total weighted minimum distance (WMD). Their approach finds an optimal solution in O(n²) time and O(n³) time, respectively, with better performance for special trees such as paths and stars. We propose here an O(nlogn) algorithm for the MWD problem on trees of arbitrary shape. We also briefly discuss the WMD case and argue that it can be solved in time. However, a systematic exposition of the later case cannot be contained in this paper.     

Dirichlet problem for semilinear edge-degenerate elliptic equations with singular potential term

In this paper, we introduce weighted p-Sobolev spaces on manifolds with edge singularities. We give the proof for the corresponding edge type Sobolev inequality, Poincaré inequality and Hardy inequality. As an application of these inequalities, we prove the existence of nontrivial weak solutions for the Dirichlet problem of semilinear elliptic equations with singular potentials on manifolds with edge singularities.     

Polyhedral studies on the convex recoloring problem

A coloring of the vertices of a graph G is convex if, for each assigned color d, the vertices with color d induce a connected subgraph of G. We address the convex recoloring problem, defined as follows. Given a graph G and a coloring of its vertices, recolor a minimum number of vertices of G, so that the resulting coloring is convex. This problem is known to be NP-hard even when G is a path. We show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and discuss separation algorithms.     

An O(m log n) algorithm for the max + sum spanning tree problem

In a graph in which each edge has two weights, the max + sum spanning tree problem seeks a spanning tree that has the minimum value for the combined total of the maximum of one of the edge weights and the sum of the other weights among all the spanning trees in the graph. Exploiting an efficient data structure, an O(m log n) algorithm is presented for solving this problem. This improves the currently known bound of O(mn).     

On Bipartite and Multipartite Clique Problems

In this paper, we introduce the maximum edge biclique problem in bipartite graphs and the edge/node weighted multipartite clique problem in multipartite graphs. Our motivation for studying these problems came from abstractions of real manufacturing problems in the computer industry and from formal concept analysis. We show that the weighted version and four variants of the unweighted version of the biclique problem are NP-complete. For random bipartite graphs, we show that the size of the maximum balanced biclique is considerably smaller than the size of the maximum edge cardinality biclique, thus highlighting the difference between the two problems. For multipartite graphs, we consider three versions each for the edge and node weighted problems which differ in the structure of the multipartite clique (MPC) required. We show that all the edge weighted versions are NP-complete in general. We also provide a special case in which edge weighted versions are polynomially solvable.     

On edge-weighted recursive trees and inversions in random permutations

We introduce random recursive trees, where deterministically weights are attached to the edges according to the labeling of the trees. We will give a bijection between recursive trees and permutations, which relates the arising edge-weights in recursive trees with inversions of the corresponding permutations. Using this bijection we obtain exact and limiting distribution results for the number of permutations of size n, where exactly m elements have j inversions. Furthermore we analyze the distribution of the sum of labels of the elements, which have exactly j inversions, where we can identify Dickman's infinitely divisible distribution as the limit law. Moreover we give a distributional analysis of weighted depths and weighted distances in edge-weighted recursive trees.     

Arithmetic returns for investment performance measurement

This paper introduces new money-weighted metrics for investment performance analysis, based on arithmetic means of holding period rates weighted by the investment’s market values. This approach generates rates of return which measure a fund’s or portfolio’s performance and a fund manager’s performance. It also enables to show that the Internal Rate of Return (IRR) is a weighted mean of holding period rates associated with interim values which differ from market values, so that value additivity is violated. The manager’s Arithmetic Internal Rate of Return (AIRR) is shown to be the true period equivalent of the cumulative Time Weighted Rate of Return (TWRR), whereas the period TWRR (a geometric return) provides a different ranking. The method is easily generalized for coping with varying benchmark rates. We also cope with the practical problem of estimating interim values whenever they are not available.