突发性片堵塞下两车信息共享的加拿大旅行者问题

提出突发性片堵塞下两车信息共享的加拿大旅行者问题,即两车欲从起点出发去终点,在运输过程中会遭遇突发性片堵塞,若两车对堵塞信息都能有限预知且车辆间可以信息共享,如何制定路径选择策略使两车花费的总时间尽可能少。针对该问题,采用在线问题与竞争策略的理论和方法,建立突发性片堵塞下两车信息共享的在线路径选择模型,设计混合贪婪策略,结合片堵塞中多条路段同时发生堵塞的特点,以及所选路径是否经过信息预知点到片堵塞起始点的路段（预知路段）等策略不同情形的分析,证明混合贪婪策略竞争比。最后进行实例分析,验证模型和策略的有效性。     

An efficient approach for large scale graph partitioning

In this paper, we consider the problem of partitioning the set of vertices of a graph intok subsets of approximately the same cardinality in such a way that the number of edges whose endpoints are in different subsets is minimized. A greedy heuristic, called Procedure1, based on the independent growth of each subset by fronts is proposed for constructing a good-quality graph partition. In addition, we present a more sophisticated version of the greedy heuristic, called Procedure2, which periodically calls a routine to refine the partition being built. We show that the partitions generated by Procedure1 are competitive with those obtained by several constructive heuristics in the literature, e.g. spectral, geometric, as well as other greedy heuristics. Moreover, the partitions produced by Procedure2 are compared with those produced by a leading graph partitioning method in the literature.     

Approximating the Minimum k-way Cut in a Graph via Minimum 3-way Cuts

For an edge weighted undirected graph G and an integer k > 2, a k-way cut is a set of edges whose removal leaves G with at least k components. We propose a simple approximation algorithm to the minimum k-way cut problem. It computes a nearly optimal k-way cut by using a set of minimum 3-way cuts. We show that the performance ratio of our algorithm is 2 – 3/k for an odd k and 2 – (3k – 4)/(k ² – k) for an even k. The running time is O(kmn ³ log(n ²/m)) where n and m are the numbers of vertices and edges respectively.     

Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree

Given a simple, undirected graph G=(V,E) and a weight function w:E→ℤ⁺, we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. It has previously been shown that the unweighted version of the problem is solvable in polynomial time while the weighted version is (weakly) NP-hard. In this paper, we strengthen these results as follows: (1) We prove that the weighted version is strongly NP-hard even if all edge weights belong to the set {1,k}, where k is any fixed integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm for this problem whose approximation ratio is smaller than (1+1/k) unless P = NP; (2) we present a new polynomial-time algorithm that approximates the general version of the problem within a ratio of (2−1/k), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1,k} within a ratio of 3/2 for k=2 (note that this matches the inapproximability bound above), and (2−2/(k+1)) for any k≥3, respectively, in polynomial time.     

Necessary Edges in k-Chordalisations of Graphs

A k-chordalisation of a graph G = (V,E) is a graph H = (V,F) obtained by adding edges to G, such that H is a chordal graph with maximum clique size at most k. This note considers the problem: given a graph G = (V,E) which pairs of vertices, non-adjacent in G, will be an edge in every k-chordalisation of G. Such a pair is called necessary for treewidth k. An equivalent formulation is: which edges can one add to a graph G such that every tree decomposition of G of width at most k is also a tree decomposition of the resulting graph G. Some sufficient, and some necessary and sufficient conditions are given for pairs of vertices to be necessary for treewidth k. For a fixed k, one can find in linear time for a given graph G the set of all necessary pairs for treewidth k. If k is given as part of the input, then this problem is coNP-hard. A few similar results are given when interval graphs (and hence pathwidth) are used instead of chordal graphs and treewidth.     

Packing <Emphasis Type="Bold">[1, Δ]</Emphasis>-factors in graphs of small degree

Given an undirected, connected graph G with maximum degree Δ, we introduce the concept of a [1, Δ]-factor k-packing in G, defined as a set of k edge-disjoint subgraphs of G such that every vertex of G has an incident edge in at least one subgraph. The problem of deciding whether a graph admits a [1,Δ]-factor k-packing is shown to be solvable in linear time for k = 2, but NP-complete for all k≥ 3. For k = 2, the optimisation problem of minimising the total number of edges of the subgraphs of the packing is NP-hard even when restricted to subcubic planar graphs, but can in general be approximated within a factor of by reduction to the Maximum 2-Edge-Colorable Subgraph problem. Finally, we discuss implications of the obtained results for the problem of fault-tolerant guarding of a grid, which provides the main motivation for research.     

Robot Map Verification of a Graph World

In the map verification problem, a robot is given a (possibly incorrect) map M of the world G with its position and orientation indicated on the map. The task is to find out whether this map, for the given robot position and its orientation in the map, is correct for the world G. We consider the world model of a graph G = (V _G, E _G) in which, for each vertex, edges incident to the vertex are ordered cyclically around that vertex. (This also holds for the map M = (V _M, E _M.) The robot can traverse edges and enumerate edges incident on the current vertex, but it cannot distinguish vertices (and edges) from each other. To solve the verification problem, the robot uses a portable edge marker, that it can put down at an edge of the graph world G and pick up later as needed. The robot can recognize the edge marker when it encounters it in the world G. By reducing the verification problem to an exploration problem, verification can be completed in O(|V _G| × |E _G|) edge traversals (the mechanical cost) with the help of a single vertex marker which can be dropped and picked up at vertices of the graph world (G. Dudek, M. Jenkin, E. Milios, and D. Wilkes, IEEE Trans. on Robotics and Automation, vol. 7, pp. 859–865, 1991; Robotics and Autonomous Systems, vol. 22(2), pp. 159–178, 1997). In this paper, we show a strategy that verifies a map in O(|V _M|) edge traversals only, using a single edge marker, when M is a plane embedded graph, even though G may not be planar (e.g., G may contain overpasses, tunnels, etc.).     

The robot cleans up

Imagine a large building with many corridors. A robot cleans these corridors in a greedy fashion, the next corridor cleaned is always the dirtiest to which it is incident. We determine bounds on the minimum s(G) and maximum S(G) number of time steps (over all edge weightings) before every edge of a graph G has been cleaned. We show that Eulerian graphs have a self-stabilizing property that holds for any initial edge weighting: after the initial cleaning of all edges, all subsequent cleanings require s(G) time steps. Finally, we show the only self-stabilizing trees are a subset of the superstars.     

The max quasi-independent set problem

In this paper, we deal with the problem of finding quasi-independent sets in graphs. This problem is formally defined in three versions, which are shown to be polynomially equivalent. The one that looks most general, namely, f-max quasi-independent set, consists of, given a graph and a non-decreasing function f, finding a maximum size subset Q of the vertices of the graph, such that the number of edges in the induced subgraph is less than or equal to f(|Q|). For this problem, we show an exact solution method that runs within time O^*(2^{\fracd-27/23d+1n})O^{*}(2^{\frac{d-27/23}{d+1}n}) on graphs of average degree bounded by d. For the most specifically defined γ-max quasi-independent set and k-max quasi-independent set problems, several results on complexity and approximation are shown, and greedy algorithms are proposed, analyzed and tested.     

Complexity of determining the most vital elements for the p-median and p-center location problems

We consider the k most vital edges (nodes) and min edge (node) blocker versions of the p-median and p-center location problems. Given a weighted connected graph with distances on edges and weights on nodes, the k most vital edges (nodes) p-median (respectively p-center) problem consists of finding a subset of k edges (nodes) whose removal from the graph leads to an optimal solution for the p-median (respectively p-center) problem with the largest total weighted distance (respectively maximum weighted distance). The complementary problem, min edge (node) blocker p-median (respectively p-center), consists of removing a subset of edges (nodes) of minimum cardinality such that an optimal solution for the p-median (respectively p-center) problem has a total weighted distance (respectively a maximum weighted distance) at least as large as a specified threshold. We show that k most vital edges p-median and k most vital edges p-center are NP-hard to approximate within a factor $\frac{7}{5}-\epsilon$ and $\frac{4}{3}-\epsilon$ respectively, for any ?>0, while k most vital nodes p-median and k most vital nodes p-center are NP-hard to approximate within a factor $\frac{3}{2}-\epsilon$ , for any ?>0. We also show that the complementary versions of these four problems are NP-hard to approximate within a factor 1.36.     

On minimum <Emphasis Type="Italic">m</Emphasis>-connected <Emphasis Type="Italic">k</Emphasis>-dominating set problem in unit disc graphs

Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S⊆V of minimal size such that every vertex in V∖S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m≤2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m. This work was supported in part by the Research Grants Council of Hong Kong under Grant No. CityU 1165/04E, the National Natural Science Foundation of China under Grant No. 70221001, 10531070 and 10771209.     

Strongly chordal and chordal bipartite graphs are sandwich monotone

A graph class is sandwich monotone if, for every pair of its graphs G ₁=(V,E ₁) and G ₂=(V,E ₂) with E ₁⊂E ₂, there is an ordering e ₁,…,e _k of the edges in E ₂∖E ₁ such that G=(V,E ₁∪{e ₁,…,e _i }) belongs to the class for every i between 1 and k. In this paper we show that strongly chordal graphs and chordal bipartite graphs are sandwich monotone, answering an open question by Bakonyi and Bono (Czechoslov. Math. J. 46:577–583, 1997). So far, very few classes have been proved to be sandwich monotone, and the most famous of these are chordal graphs. Sandwich monotonicity of a graph class implies that minimal completions of arbitrary graphs into that class can be recognized and computed in polynomial time. For minimal completions into strongly chordal or chordal bipartite graphs no polynomial-time algorithm has been known. With our results such algorithms follow for both classes. In addition, from our results it follows that all strongly chordal graphs and all chordal bipartite graphs with edge constraints can be listed efficiently.     

An Edge-Splitting Algorithm in Planar Graphs

For a multigraph G = (V, E), let s V be a designated vertex which has an even degree, and let _G (V – s) denote min{c _G(X) | Ø X V – s}, where c _G(X) denotes the size of cut X. Splitting two adjacent edges (s, u) and (s, v) means deleting these edges and adding a new edge (u, v). For an integer k, splitting two edges e ₁ and e ₂ incident to s is called (k, s)-feasible if _G(V – s) k holds in the resulting graph G. In this paper, we prove that, for a planar graph G and an even k or k = 3 with k _G (V – s), there exists a complete (k, s)-feasible splitting at s such that the resulting graph G is still planar, and present an O(n ³ log n) time algorithm for finding such a splitting, where n = |V|. However, for every odd k 5, there is a planar graph G with a vertex s which has no complete (k, s)-feasible and planarity-preserving splitting. As an application of this result, we show that for an outerplanar graph G and an even integer k the problem of optimally augmenting G to a k-edge-connected planar graph can be solved in O(n ³ log n) time.     

Tree edge decomposition with an application to minimum ultrametric tree approximation

A k-decomposition of a tree is a process in which the tree is recursively partitioned into k edge-disjoint subtrees until each subtree contains only one edge. We investigated the problem how many levels it is sufficient to decompose the edges of a tree. In this paper, we show that any n-edge tree can be 2-decomposed (and 3-decomposed) within at most ⌈1.44 log n⌉ (and ⌈log n⌉ respectively) levels. Extreme trees are given to show that the bounds are asymptotically tight. Based on the result, we designed an improved approximation algorithm for the minimum ultrametric tree.     

Linear time construction of 5-phylogenetic roots for tree chordal graphs

Inspired by phylogenetic tree construction in computational biology, Lin et al. (The 11th Annual International Symposium on Algorithms and Computation (ISAAC 2000), pp. 539–551, 2000) introduced the notion of a k -phylogenetic root. A k-phylogenetic root of a graph G is a tree T such that the leaves of T are the vertices of G, two vertices are adjacent in G precisely if they are within distance k in T, and all non-leaf vertices of T have degree at least three. The k-phylogenetic root problem is to decide whether such a tree T exists for a given graph G. In addition to introducing this problem, Lin et al. designed linear time constructive algorithms for k≤4, while left the problem open for k≥5. In this paper, we partially fill this hole by giving a linear time constructive algorithm to decide whether a given tree chordal graph has a 5-phylogenetic root; this is the largest class of graphs known to have such a construction.     

On broadcasting in unicyclic graphs

Broadcasting is an information dissemination problem in a connected network, in which one node, called the originator, disseminates a message to all other nodes by placing a series of calls along the communication lines of the network. Finding the broadcast time of a vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for trees. In this paper we present a linear algorithm that determines the broadcast time of any originator in an arbitrary unicyclic graph. As a byproduct, we find a broadcast center of the unicyclic graph. We also present an O(|V|+k ²) algorithm to find the broadcast time of an arbitrary unicyclic graph, where k is the length of the cycle. In the last section we give tight lower and upper bounds on broadcast time of a spanning tree based on the broadcast time of the unicyclic graph. The results of Sects. 2, 3 and most of the proofs in Sects. 2, 3 of this paper are presented by Harutyunyan and Maraachlian (Proceedings of 13th annual COCOON, pp. 372–383, 2007). All results in Sects. 4, 5 and the complete proof of Theorem 3 are new results.     

A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions

Given a graph G=(V,E) with edge weights w _e ∈ℝ, the optimum cooperation problem consists in determining a partition of the graph that maximizes the sum of weights of the edges with nodes in the same class plus the number of the classes of the partition. The problem is also known in the literature as the optimum attack problem in networks. Furthermore, a relevant physics application exists.     

Inapproximability and approximability of maximal tree routing and coloring

Let G be a undirected connected graph. Given g groups each being a subset of V(G) and a number of colors, we consider how to find a subgroup of subsets such that there exists a tree interconnecting all vertices in each subset and all trees can be colored properly with given colors (no two trees sharing a common edge receive the same color); the objective is to maximize the number of subsets in the subgroup. This problem arises from the application of multicast communication in all optical networks. In this paper, we first obtain an explicit lower bound on the approximability of this problem and prove Ω(g^1−ε)-inapproximability even when G is a mesh. We then propose a simple greedy algorithm that achieves performance ratio O√|E(G)|, which matches the theoretical bounds. Supported in part by the NSF of China under Grant No. 70221001 and 60373012.     

Incrementing Bipartite Digraph Edge-Connectivity

This paper solves the problem of increasing the edge-connectivity of a bipartite digraph by adding the smallest number of new edges that preserve bipartiteness. A natural application arises when we wish to reinforce a 2-dimensional square grid framework with cables. We actually solve the more general problem of covering a crossing family of sets with the smallest number of directed edges, where each new edge must join the blocks of a given bipartition of the elements. The smallest number of new edges is given by a min-max formula that has six infinite families of exceptional cases. We discuss a problem on network flows whose solution has a similar formula with three infinite families of exceptional cases. We also discuss a problem on arborescences whose solution has five infinite families of exceptions. We give an algorithm that increases the edge-connectivity of a bipartite digraph in the same time as the best-known algorithm for the problem without the bipartite constraint: O(km log n) for unweighted digraphs and O(nm log (n ²/m)) for weighted digraphs, where n, m and k are the number of vertices and edges of the given graph and the target connectivity, respectively.     

Minimum Cost Edge Subset Covering Exactly k Vertices of a Graph

Given a graph G with nonnegative edge costs and an integer k, we consider the problem of finding an edge subset S of minimum total cost with respect to the constraint that S covers exactly k vertices of G. An O(n ³) algorithm is presented where n is the order of G. It is based on the author's previous paper dealing with a similar problem asking S to cover at least k vertices.