Improved Algorithms for Some Competitive Location Centroid Problems on Paths, Trees and Graphs

We consider a common scenario in competitive location, where two competitors (providers) place their facilities (servers) on a network, and the users, which are modeled by the nodes of the network, can choose between the providers. We assume that each user has an inelastic demand, specified by a positive real weight. A user is fully served by a closest facility. The benefit (gain) of a competitor is his market share, i.e., the total weight (demand) of the users served at his facilities. In our scenario the two providers, called the leader and the follower, sequentially place p and r servers, respectively. After the leader selects the locations for his p servers, the follower will determine the optimal locations for his r servers, that maximize his benefit. An (r,p)-centroid is a set of locations for the p servers of the leader, that will minimize the maximum gain of the follower who can establish r servers. In this paper we focus mainly on the cases where either the leader or the follower can establish only one facility, i.e., either p=1, or r=1. We consider two versions of the model. In the discrete case the facilities can be established only at the nodes, while in the absolute case they can be established anywhere on the network. For the (r,1)-centroid problem, we show that it is strongly NP-hard for a general graph, but can be approximated within a factor e/(e?1). On the other hand, when the graph is a tree, we provide strongly polynomial algorithms for the (r,p)-centroid model, whenever p is fixed. For the (1,1)-centroid problem on a general graph, we improve upon known results, and give the first strongly polynomial algorithm. The discrete (1,p)-centroid problem has been known to be NP-hard even for a subclass of series-parallel graphs with pathwidth bounded by 6. In view of this result, we consider the discrete and absolute (1,p) centroid models on a tree, and present the first strongly polynomial algorithms. Further improvements are shown when the tree is a path.     

How to Use Spanning Trees to Navigate in Graphs

In this paper, we investigate three strategies of how to use a spanning tree T of a graph G to navigate in G, i.e., to move from a current vertex x towards a destination vertex y via a path that is close to optimal. In each strategy, each vertex v has full knowledge of its neighborhood N _G [v] in G (or, k-neighborhood D _k (v,G), where k is a small integer) and uses a small piece of global information from spanning tree T (e.g., distance or ancestry information in T), available locally at v, to navigate in G. We investigate advantages and limitations of these strategies on particular families of graphs such as graphs with locally connected spanning trees, graphs with bounded length of largest induced cycle, graphs with bounded tree-length, graphs with bounded hyperbolicity. For most of these families of graphs, the ancestry information from a Breadth-First-Search-tree guarantees short enough routing paths. In many cases, the obtained results are optimal up to a constant factor.     

All-Pairs Bottleneck Paths in Vertex Weighted Graphs

Let G=(V,E,w) be a directed graph, where w:V→ℝ is a weight function defined on its vertices. The bottleneck weight, or the capacity, of a path is the smallest weight of a vertex on the path. For two vertices u,v the capacity from u to v, denoted by c(u,v), is the maximum bottleneck weight of a path from u to v. In the All-Pairs Bottleneck Paths (APBP) problem the task is to find the capacities for all ordered pairs of vertices. Our main result is an O(n ^2.575) time algorithm for APBP. The exponent is derived from the exponent of fast matrix multiplication.     

Optimal Independent Spanning Trees on Odd Graphs

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and bandwidth. The designs of multiple ISTs on several classes of networks have been widely investigated. In this paper we show a construction algorithm of ISTs on odd graphs, and we analyze that all the lengths of the paths in the ISTs are less than or equal to the length of the shortest path+4, which is optimal. We also prove that the heights of the ISTs we constructed are d+1, which again is optimal, since the fault diameter of an odd graph is d+1.     

Pathfinder: Visual Analysis of Paths in Graphs

The analysis of paths in graphs is highly relevant in many domains. Typically, path‐related tasks are performed in node‐link layouts. Unfortunately, graph layouts often do not scale to the size of many real world networks. Also, many networks are multivariate, i.e., contain rich attribute sets associated with the nodes and edges. These attributes are often critical in judging paths, but directly visualizing attributes in a graph layout exacerbates the scalability problem. In this paper, we present visual analysis solutions dedicated to path‐related tasks in large and highly multivariate graphs. We show that by focusing on paths, we can address the scalability problem of multivariate graph visualization, equipping analysts with a powerful tool to explore large graphs. We introduce Pathfinder, a technique that provides visual methods to query paths, while considering various constraints. The resulting set of paths is visualized in both a ranked list and as a node‐link diagram. For the paths in the list, we display rich attribute data associated with nodes and edges, and the node‐link diagram provides topological context. The paths can be ranked based on topological properties, such as path length or average node degree, and scores derived from attribute data. Pathfinder is designed to scale to graphs with tens of thousands of nodes and edges by employing strategies such as incremental query results. We demonstrate Pathfinder's fitness for use in scenarios with data from a coauthor network and biological pathways.     

Embedding Complete Binary Trees into Star and Pancake Graphs

Let G and H be two simple undirected graphs. An embedding of the graph G into the graph H is an injective mapping f from the vertices of G to the vertices of H . The dilation of the embedding is the maximum distance between f(u),f(v) taken over all edges (u,v) of G . We give a construction of embeddings of dilation 1 of complete binary trees into star graphs. The height of the trees embedded with dilation 1 into the n -dimensional star graph is Ω (n log n) , which is asymptotically optimal. Constructions of embeddings of complete binary trees of dilation 2δ and 2δ +1 , δ≥ 1, into star graphs are given. The use of larger dilation allows embeddings of trees of greater height into star graphs. It is shown that all these constructions can be modified to yield embeddings of dilation 1 and 2δ , δ≥ 1 , of complete binary trees into pancake graphs. Received February 1996, and in final form October 1997.     

A Quadratic Algorithm for Finding Next-to-Shortest Paths in Graphs

Given an edge-weighted undirected graph G and two prescribed vertices u and v, a next-to-shortest (u,v)-path is a shortest (u,v)-path amongst all (u,v)-paths having length strictly greater than the length of a shortest (u,v)-path. In this paper, we deal with the problem of computing a next-to-shortest (u,v)-path. We propose an O(n²){\mathcal{O}}(n^{2}) time algorithm for solving this problem, which significantly improves the bound of a previous one in O(n³){\mathcal{O}}(n^{3}) time where n is the number of vertices in G.     

A Preemptive Algorithm for Maximizing Disjoint Paths on Trees

We consider the on-line version of the maximum vertex disjoint path problem when the underlying network is a tree. In this problem, a sequence of requests arrives in an on-line fashion, where every request is a path in the tree. The on-line algorithm may accept a request only if it does not share a vertex with a previously accepted request. The goal is to maximize the number of accepted requests. It is known that no on-line algorithm can have a competitive ratio better than Ω(log n) for this problem, even if the algorithm is randomized and the tree is simply a line. Obviously, it is desirable to beat the logarithmic lower bound. Adler and Azar (Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithm, pp. 1–10, 1999) showed that if preemption is allowed (namely, previously accepted requests may be discarded, but once a request is discarded it can no longer be accepted), then there is a randomized on-line algorithm that achieves constant competitive ratio on the line. In the current work we present a randomized on-line algorithm with preemption that has constant competitive ratio on any tree. Our results carry over to the related problem of maximizing the number of accepted paths subject to a capacity constraint on vertices (in the disjoint path problem this capacity is 1). Moreover, if the available capacity is at least 4, randomization is not needed and our on-line algorithm becomes deterministic.     

Minimal Expansions in Redundant Number Systems and Shortest Paths in Graphs

We consider digit expansions in redundant number systems to base q with and consider such an expansion as minimal, if is minimal. We describe an efficient algorithm for determining a minimal representation and give an explicit characterization of optimal representations for odd q. Received: July 20, 1999; revised August 23 1999     

带权区间图的最短路算法

提出一个解带权区间图的最短路问题的O(nα(n))时间新算法，其中n是带权区间图中带权区间的个数，α(n)是单变量Ackerman函数的逆函数，它是一个增长速度比log n慢得多的函数，对于通常所见到的n，α(n)≤4．本文提出的新算法不仅在时间复杂性上比直接用Dijkstra算法解带权区间图的最短路问题有较大改进，而且算法设计思想简单，易于理解和实现．     

Two fixed-parameter algorithms for Vertex Covering by Paths on Trees

Vertex Covering by Paths on Trees with applications in machine translation is the task to cover all vertices of a tree T=(V,E) by choosing a minimum-weight subset of given paths in the tree. The problem is NP-hard and has recently been solved by an exact algorithm running in O(C⁴⋅²|V|) time, where C denotes the maximum number of paths covering a tree vertex. We improve this running time to O(C²⋅C⋅|V|). On the route to this, we introduce the problem Tree-like Weighted Hitting Set which might be of independent interest. In addition, for the unweighted case of Vertex Covering by Paths on Trees, we present an exact algorithm using a search tree of size O(k²⋅k!), where k denotes the number of chosen covering paths. Finally, we briefly discuss the existence of a size-O(k²) problem kernel.     

A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs

In this paper we give a fully dynamic approximation scheme for maintaining all-pairs shortest paths in planar networks. Given an error parameter such that , our algorithm maintains approximate all-pairs shortest paths in an undirected planar graph G with nonnegative edge lengths. The approximate paths are guaranteed to be accurate to within a 1+ factor. The time bounds for both query and update for our algorithm is O( ^-1 n ^2/3 log ² n log D) , where n is the number of nodes in G and D is the sum of its edge lengths. The time bound for the queries is worst case, while that for the additions is amortized. Our approximation algorithm is based upon a novel technique for approximately representing all-pairs shortest paths among a selected subset of the nodes by a sparse substitute graph. Received January 1995; revised February 1997.     

Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult

We consider the problem of coloring a planar graph with the minimum number of colors so that each color class avoids one or more forbidden graphs as subgraphs. We perform a detailed study of the computational complexity of this problem. We present a complete picture for the case with a single forbidden connected (induced or noninduced) subgraph. The 2-coloring problem is NP-hard if the forbidden subgraph is a tree with at least two edges, and it is polynomially solvable in all other cases. The 3-coloring problem is NP-hard if the forbidden subgraph is a path with at least one edge, and it is polynomially solvable in all other cases. We also derive results for several forbidden sets of cycles. In particular, we prove that it is NP-complete to decide if a planar graph can be 2-colored so that no cycle of length at most 5 is monochromatic.     

Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs

We study the problem of packing element-disjoint Steiner trees in graphs. We are given a graph and a designated subset of terminal nodes, and the goal is to find a maximum cardinality set of element-disjoint trees such that each tree contains every terminal node. An element means a non-terminal node or an edge. (Thus, each non-terminal node and each edge must be in at most one of the trees.) We show that the problem is APX-hard when there are only three terminal nodes, thus answering an open question. Our main focus is on the special case when the graph is planar. We show that the problem of finding two element-disjoint Steiner trees in a planar graph is NP-hard. Similarly, the problem of finding two edge-disjoint Steiner trees in a planar graph is NP-hard. We design an algorithm for planar graphs that achieves an approximation guarantee close to 2. In fact, given a planar graph that is k element-connected on the terminals (k is an upper bound on the number of element-disjoint Steiner trees), the algorithm returns $\lfloor\frac{k}{2} \rfloor-1$ element-disjoint Steiner trees. Using this algorithm, we get an approximation algorithm for the edge-disjoint version of the problem on planar graphs that improves on the previous approximation guarantees. We also show that the natural LP relaxation of the planar problem has an integrality ratio approaching?2.     

A Linear-Time Algorithm for Finding Locally Connected Spanning Trees on Circular-Arc Graphs

Suppose that T is a spanning tree of a graph G. T is called a locally connected spanning tree of G if for every vertex of T, the set of all its neighbors in T induces a connected subgraph of G. In this paper, given an intersection model of a circular-arc graph, an O(n)-time algorithm is proposed that can determine whether the circular-arc graph contains a locally connected spanning tree or not, and produce one if it exists.     

A Flexible Algorithm for Generating All the Spanning Trees in Undirected Graphs

In this paper we propose an algorithm for generating all the spanning trees in undirected graphs. The algorithm requires O (n+m+ τ n) time where the given graph has n vertices, m edges, and τ spanning trees. For outputting all the spanning trees explicitly, this time complexity is optimal. Our algorithm follows a special rooted tree structure on the skeleton graph of the spanning tree polytope. The rule by which the rooted tree structure is traversed is irrelevant to the time complexity. In this sense, our algorithm is flexible. If we employ the depth-first search rule, we can save the memory requirement to O (n+m). A breadth-first implementation requires as much as O (m+ τ n) space, but when a parallel computer is available, this might have an advantage. When a given graph is weighted, the best-first search rule provides a ranking algorithm for the minimum spanning tree problem. The ranking algorithm requires O (n+ m + τ n) time and O (m+ τ n) space when we have a minimum spanning tree. Received January 21, 1995; revised February 19, 1996.     

网树求解有向无环图中具有长度约束的简单路径和最长路径问题

具有长度约束的简单路径(Simple Paths with Length Constraint,SPLC)问题是指求解图中任意两点间路径长度为m的简单路径数,是k-path问题的一种特殊情况.该文基于网树数据结构提出了在有向无环图中求解SPLC问题的算法(Nettree for SPLC in Directed Acyclic Graphs,NSPLCDAG).网树是一种多树根多双亲的数据结构.NSPLCDAG算法将该问题转化为一棵网树后,利用树根路径数这一性质对其进行求解.对NSPLCDAG算法进行改造,可以求解有向无环图中最长路径问题并形成网树求解最长路径算法(Nettree for the Longest Path in DAGs,NLPDAG),NLPDAG算法可找到所有最长路径,对NLPDAG算法做进一步改进形成改进的NLPDAG算法,改进的NLPDAG算法可在线性时间复杂度内给出有向无环图中的一条最长路径.实验结果验证了NSPLCDAG和改进的NLPDAG算法的正确性与有效性.     

Hierarchical Segmentations with Graphs: Quasi-flat Zones,Minimum Spanning Trees,and Saliency Maps

Hierarchies of partitions are generally represented by dendrograms (direct representation). They can also be represented by saliency maps or minimum spanning trees. In this article, we precisely study the links between these three representations. In particular, we provide a new bijection between saliency maps and hierarchies based on quasi-flat zones as often used in image processing and we characterize saliency maps and minimum spanning trees as solutions to constrained minimization problems where the constraint is quasi-flat zones preservation. In practice, these results make up a toolkit for designing new hierarchical methods where one can choose the most convenient representation. They also invite us to process non-image data with morphological hierarchies. More precisely, we show the practical interest of the proposed framework for: (i) hierarchical watershed image segmentations, (ii) combinations of different hierarchical segmentations, (iii) hierarchicalizations of some non-hierarchical image segmentation methods based on regional dissimilarities, and (iv) hierarchical analysis of geographic data.