限制性多源点偏心距增广问题

给定一个赋权图$G=（V,E;w,c）$以及图$G$的一个支撑子图$G_{1}=（V,E_{1}）$,这里源点集合$S=\{s_{1},s_{2},\cdots,s_{k}\}\subseteq V$,权重函数$w：E\rightarrow\mathbb{R}^{+}$,费用函数$c：E\setminus E_{1}\rightarrow\mathbb{Z}^{+}$和一个正整数$B$,本文考虑两类限制性多源点偏心距增广问题,具体叙述如下：（1）限制性多源点最小偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最小值达到最小;（2）限制性多源点最大偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。     

限制性多源点偏心距增广问题

给定一个赋权图$G=（V,E;w,c）$以及图$G$的一个支撑子图$G_{1}=（V,E_{1}）$,这里源点集合$S=\{s_{1},s_{2},\cdots,s_{k}\}\subseteq V$,权重函数$w：E\rightarrow\mathbb{R}^{+}$,费用函数$c：E\setminus E_{1}\rightarrow\mathbb{Z}^{+}$和一个正整数$B$,本文考虑两类限制性多源点偏心距增广问题,具体叙述如下：（1）限制性多源点最小偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最小值达到最小;（2）限制性多源点最大偏心距增广问题是要寻找一个边子集$E_{2}\subseteq E\setminus E_{1}$,满足约束条件$c（E_{2}）$$\leq$$B$,目标是使得子图$G_{1}\cup E_{2}$上源点集$S$中顶点偏心距的最大值达到最小。本文设计了两个固定参数可解的常数近似算法来分别对上述两类问题进行求解。     

Extremal graphs in connectivity augmentation

Let A(n, k, t) denote the smallest integer e for which every k‐connected graph on n vertices can be made (k + t)‐connected by adding e new edges. We determine A(n, k, t) for all values of n, k, and t in the case of (directed and undirected) edge‐connectivity and also for directed vertex‐connectivity. For undirected vertex‐connectivity we determine A(n, k, 1) for all values of n and k. We also describe the graphs that attain the extremal values. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 179–193, 1999     

Parallel and fast sequential algorithms for undirected edge connectivity augmentation

1 ,E₂,..., such that ⋃_i≤τE_i optmially increases the connectivity by τ, for any integer τ. The main result of the paper is that this sequence of edge sets can be divided into O(n) groups such that within one group, all E_i are basically the same. Using this result, we improve on the running time of edge connectivity augmentation, as well as we give the first parallel (RNC) augmentation algorithm. We also present new efficient subroutines for finding the so-called extreme sets and the cactus representation of min-cuts required in our algorithms. Augmenting the connectivity of hypergraphs with ordinary edges is known to be structurally harder than that of ordinary graphs. In a weaker version when one exceptional hyperedge is allowed in the augmenting edge set, we derive similar results as for ordinary graphs. Received November 1995 / Revised version received July 1998 Published online March 16, 1999     

On algebraic connectivity augmentation

Suppose that G is an undirected graph, and that H is a spanning subgraph of G^c whose edges induce a subgraph on p vertices. We consider the expression α(G∪H)-α(G), where α denotes the algebraic connectivity. Specifically, we provide upper and lower bounds on α(G∪H)-α(G) in terms of p, and characterise the corresponding equality cases. We also discuss the density of the expression α(G∪H)-α(G) in the interval [0,p]. A bound on α(G∪H)-α(G) is provided in a special case, and several examples are considered.     

Optimal on-line flow time with resource augmentation

We study the problem of scheduling n jobs that arrive over time. We consider a non-preemptive setting on a single machine. The goal is to minimize the total flow time. We use extra resource competitive analysis: an optimal off-line algorithm which schedules jobs on a single machine is compared to a more powerful on-line algorithm that has ? machines. We design an algorithm of competitive ratio , where Δ is the maximum ratio between two job sizes, and provide a lower bound which shows that the algorithm is optimal up to a constant factor for any constant ?. The algorithm works for a hard version of the problem where the sizes of the smallest and the largest jobs are not known in advance, only Δ and n are known. This gives a trade-off between the resource augmentation and the competitive ratio.We also consider scheduling on parallel identical machines. In this case the optimal off-line algorithm has m machines and the on-line algorithm has ?m machines. We give a lower bound for this case. Next, we give lower bounds for algorithms using resource augmentation on the speed. Finally, we consider scheduling with hard deadlines, and scheduling so as to minimize the total completion time.     

Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs

Given an undirected multigraph G=(V,E), a family W of sets W⊆V of vertices (areas), and a requirement function r:W→Z⁺ (where Z⁺ is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least r(W) edge-disjoint paths between v and W for every pair of a vertex v∈V and an area W∈W. So far this problem was shown to be NP-hard in the uniform case of r(W)=1 for each W∈W, and polynomially solvable in the uniform case of r(W)=r?2 for each W∈W. In this paper, we show that the problem can be solved in time, even if r(W)?2 holds for each W∈W, where n=|V|, m=|{{u,v}|(u,v)∈E}|, p=|W|, and r^*=max{r(W)∣W∈W}.     

On total domination vertex critical graphs of high connectivity

A graph is called γ-critical if the removal of any vertex from the graph decreases the domination number, while a graph with no isolated vertex is γ_t-critical if the removal of any vertex that is not adjacent to a vertex of degree 1 decreases the total domination number. A γ_t-critical graph that has total domination number k, is called k-γ_t-critical. In this paper, we introduce a class of k-γ_t-critical graphs of high connectivity for each integer k≥3. In particular, we provide a partial answer to the question “Which graphs are γ-critical and γ_t-critical or one but not the other?” posed in a recent work [W. Goddard, T.W. Haynes, M.A. Henning, L.C. van der Merwe, The diameter of total domination vertex critical graphs, Discrete Math. 286 (2004) 255-261].     

Resource augmentation in two-dimensional packing with orthogonal rotations

We consider the problem of packing two-dimensional rectangles into the minimum number of unit squares, when 90^° rotations are allowed. Our main contribution is a polynomial-time algorithm for packing rectangles into at most OPT bins whose sides have length (1+ε), for any positive ε. Additionally, we show near-optimal packing results for a number of related packing problems.     

On the invariant translation approximation property for discrete groups

Recently J.Roe considered the question of whether for a discrete group the reduced group -algebra is the fixed point algebra of Ad acting on the uniform Roe algebra . is said to have the invariant translation approximation property in this case. We consider a slight generalization of this property which, for exact , is equivalent to the operator space approximation property of . We also give a new characterization of exactness and a short proof of the equivalence of exactness of and exactness of for discrete groups.

     

Finding maximum subgraphs with relatively large vertex connectivity

We consider a clique relaxation model based on the concept of relative vertex connectivity. It extends the classical definition of a k-vertex-connected subgraph by requiring that the minimum number of vertices whose removal results in a disconnected (or a trivial) graph is proportional to the size of this subgraph, rather than fixed at k. Consequently, we further generalize the proposed approach to require vertex-connectivity of a subgraph to be some function f of its size. We discuss connections of the proposed models with other clique relaxation ideas from the literature and demonstrate that our generalized framework, referred to as f-vertex-connectivity, encompasses other known vertex-connectivity-based models, such as s-bundle and k-block. We study related computational complexity issues and show that finding maximum subgraphs with relatively large vertex connectivity is NP-hard. An interesting special case that extends the R-robust 2-club model recently introduced in the literature, is also considered. In terms of solution techniques, we first develop general linear mixed integer programming (MIP) formulations. Then we describe an effective exact algorithm that iteratively solves a series of simpler MIPs, along with some enhancements, in order to obtain an optimal solution for the original problem. Finally, we perform computational experiments on several classes of random and real-life networks to demonstrate performance of the developed solution approaches and illustrate some properties of the proposed clique relaxation models.     

Maximum algebraic connectivity augmentation is NP-hard

The algebraic connectivity of a graph, which is the second-smallest eigenvalue of the Laplacian of the graph, is a measure of connectivity. We show that the problem of adding a specified number of edges to an input graph to maximize the algebraic connectivity of the augmented graph is NP-hard.     

Structure of augmentation quotients of finite homocyclic abelian groups

Let G be a finite abelian group and its Sylow p-subgroup a direct product of copies of a cyclic group of order p~r,i.e.,a finite homocyclic abelian group.LetΔ~n (G) denote the n-th power of the augmentation idealΔ(G) of the integral group ring ZG.The paper gives an explicit structure of the consecutive quotient group Q_n(G)=Δ~n(G)/Δ~(n 1)(G) for any natural number n and as a consequence settles a problem of Karpilovsky for this particular class of finite abelian groups.