Finding the anti-block vital edge of a shortest path between two nodes

Let P _G (s,t) denote a shortest path between two nodes s and t in an undirected graph G with nonnegative edge weights. A detour at a node u∈P _G (s,t)=(s,…,u,v,…,t) is defined as a shortest path P _G−e (u,t) from u to t which does not make use of (u,v). In this paper, we focus on the problem of finding an edge e=(u,v)∈P _G (s,t) whose removal produces a detour at node u such that the ratio of the length of P _G−e (u,t) to the length of P _G (u,t) is maximum. We define such an edge as an anti-block vital edge (AVE for short), and show that this problem can be solved in O(mn) time, where n and m denote the number of nodes and edges in the graph, respectively. Some applications of the AVE for two special traffic networks are shown. This research is supported by NSF of China under Grants 70471035, 70525004, 701210001 and 60736027, and PSF of China under Grant 20060401003.     

Efficient approximation algorithms for computing <Emphasis Type="Italic">k</Emphasis> disjoint constrained shortest paths

Let \(G=(V,\, E)\) be a given directed graph in which every edge e is associated with two nonnegative costs: a weight w(e) and a length l(e). For a pair of specified distinct vertices \(s,\, t\in V\), the k-(edge) disjoint constrained shortest path (kCSP) problem is to compute k (edge) disjoint paths between s and t, such that the total length of the paths is minimized and the weight is bounded by a given weight budget \(W\in \mathbb {R}_{0}^{+}\). The problem is known to be \({\mathcal {NP}}\)-hard, even when \(k=1\) (Garey and Johnson in Computers and intractability, 1979). Approximation algorithms with bifactor ratio \(\left( 1\,+\,\frac{1}{r},\, r\left( 1\,+\,\frac{2(\log r\,+\,1)}{r}\right) (1\,+\,\epsilon )\right) \) and \((1\,+\,\frac{1}{r},\,1\,+\,r)\) have been developed for \(k=2\) in Orda and Sprintson (IEEE INFOCOM, pp. 727–738, 2004) and Chao and Hong (IEICE Trans Inf Syst 90(2):465–472, 2007), respectively. For general k, an approximation algorithm with ratio \((1,\, O(\ln n))\) has been developed for a weaker version of kCSP, the k bi-constraint path problem which is to compute k disjoint st-paths satisfying a given length constraint and a weight constraint simultaneously (Guo et al. in COCOON, pp. 325–336, 2013). This paper first gives an approximation algorithm with bifactor ratio \((2,\,2)\) for kCSP using the LP-rounding technique. The algorithm is then improved by adopting a more sophisticated method to round edges. It is shown that for any solution output by the improved algorithm, there exists a real number \(0\le \alpha \le 2\) such that the weight and the length of the solution are bounded by \(\alpha \) times and \(2-\alpha \) times of that of an optimum solution, respectively. The key observation of the ratio proof is to show that the fractional edges, in a basic solution against the proposed linear relaxation of kCSP, exactly compose a graph in which the degree of every vertex is exactly two. At last, by a novel enhancement of the technique in Guo et al. (COCOON, pp. 325–336, 2013), the approximation ratio is further improved to \((1,\,\ln n)\).     

Special cases of the quadratic shortest path problem

The quadratic shortest path problem (QSPP) is the problem of finding a path with prespecified start vertex s and end vertex t in a digraph such that the sum of weights of arcs and the sum of interaction costs over all pairs of arcs on the path is minimized. We first consider a variant of the QSPP known as the adjacent QSPP. It was recently proven that the adjacent QSPP on cyclic digraphs cannot be approximated unless \(\hbox {P}=\hbox {NP}\). Here, we give a simple proof for the same result. We also show that if the quadratic cost matrix is a symmetric weak sum matrix and all s–t paths have the same length, then an optimal solution for the QSPP can be obtained by solving the corresponding instance of the shortest path problem. Similarly, it is shown that the QSPP with a symmetric product cost matrix is solvable in polynomial time. Further, we provide sufficient and necessary conditions for a QSPP instance on a complete symmetric digraph with four vertices to be linearizable. We also characterize linearizable QSPP instances on complete symmetric digraphs with more than four vertices. Finally, we derive an algorithm that examines whether a QSPP instance on the directed grid graph \(G_{pq}\) (\(p,q\ge 2\)) is linearizable. The complexity of this algorithm is \({\mathcal {O}(p^{3}q^{2}+p^{2}q^{3})}\).     

On optimal placement of relay nodes for reliable connectivity in wireless sensor networks

The paper addresses the relay node placement problem in two-tiered wireless sensor networks. Given a set of sensor nodes in Euclidean plane, our objective is to place minimum number of relay nodes to forward data packets from sensor nodes to the sink, such that: 1) the network is connected, 2) the network is 2-connected. For case one, we propose a (6+ε)-approximation algorithm for any ε > 0 with polynomial running time when ε is fixed. For case two, we propose two approximation algorithms with (24+ε) and (6/T+12+ε), respectively, where T is the ratio of the number of relay nodes placed in case one to the number of sensors. We further extend the results to the cases where communication radiuses of sensor nodes and relay nodes are different from each other.     

Computing an $$L_1$$ shortest path among splinegonal obstacles in the plane

Journal of Combinatorial Optimization - We reduce the problem of computing an $$L_1$$ shortest path between two given points s and t in the given splinegonal domain $$mathcal {S}$$ to the problem...     

Bounds for the traveling salesman paths of two-dimensional modular lattices

We present tight upper and lower bounds for the traveling salesman path through the points of two-dimensional modular lattices. We use these results to bound the traveling salesman path of two-dimensional Kronecker point sets. Our results rely on earlier work on shortest vectors in lattices as well as on the strong convergence of Jacobi–Perron type algorithms.     

A parameterized perspective on packing paths of length two

We study (vertex-disjoint) packings of paths of length two (i.e., of P ₂’s) in graphs under a parameterized perspective. Starting from a maximal P ₂-packing ℘ of size j we use extremal combinatorial arguments for determining how many vertices of ℘ appear in some P ₂-packing of size (j+1) (if such a packing exists). We prove that one can ‘reuse’ 2.5j vertices. We also show that this bound is asymptotically sharp. Based on a WIN-WIN approach, we build an algorithm which decides, given a graph, if a P ₂-packing of size at least k exists in time O^*(2.448^3k)\mathcal{O}^{*}(2.448^{3k}) .     

The paths embedding of the arrangement graphs with prescribed vertices in given position

Let n and k be positive integers with n?k≥2. The arrangement graph A _n,k is recognized as an attractive interconnection networks. Let x, y, and z be three different vertices of A _n,k . Let l be any integer with $d_{A_{n,k}}(\mathbf{x},\mathbf{y}) \le l \le \frac{n!}{(n-k)!}-1-d_{A_{n,k}}(\mathbf{y},\mathbf{z})$ . We shall prove the following existance properties of Hamiltonian path: (1)?for n?k≥3 or (n,k)=(3,1), there exists a Hamiltonian path R(x,y,z;l) from x to z such that d _R(x,y,z;l)(x,y)=l; (2) for n?k=2 and n≥5, there exists a Hamiltonian path R(x,y,z;l) except for the case that x, y, and z are adjacent to each other.     

Defining the Creole City by Walking: The Case of La Réunion

ABSTRACT

This paper presents exploratory work to understand the characterisation of the ‘Creole city’ inLa Réunion, through an analysis of three renovated districts. The purpose is to inform urbanrenewal programmes so that they take better account of local lifestyles and needs. Theresearch on representations and symbols involves a method to collect and analyse data thatcombines in situ situations and a strong day-to-day approach, namely, walking. This method,that may be used elsewhere, reveals the functioning qualities of traditional Creole cities as anurbanity that is adapted to its environment, and based on proximity and soft transport modes.     

The domination number of Cartesian product of two directed paths

Let γ(P _m □P _n ) be the domination number of the Cartesian product of directed paths P _m and P _n for m,n≥2. Liu et al. in (J. Comb. Optim. 22(4):651–662, 2011) determined the value of γ(P _m □P _n ) for arbitrary n and m≤6. In this work we give the exact value of γ(P _m □P _n ) for any m,n and exhibit dominating sets of minimum cardinality.     

An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph models

Link scheduling is a fundamental problem in wireless ad hoc and sensor networks. In this paper, we focus on the shortest link scheduling (SLS) under Signal-to-Interference-plus-Noise-Ratio and hypergraph models, and propose an approximation algorithm \(SLS_{pc}\) (A link scheduling algorithm with oblivious power assignment for the shortest link scheduling) with oblivious power assignment for better performance than GOW* proposed by Blough et al. [IEEE/ACM Trans Netw 18(6):1701–1712, 2010]. For the average scheduling length of \(SLS_{pc}\) is 1 / m of GOW*, where \(m=\lfloor \varDelta _{max}\cdot p \rfloor \) is the expected number of the links in the set V returned by the algorithm HyperMaxLS (Maximal links schedule under hypergraph model) and \(0<p<1\) is the constant. In the worst, ideal and average cases, the ratios of time complexity of our algorithm \(SLS_{pc}\) to that of GOW* are \(O(\varDelta _{max}/\overline{k})\), \(O(1/(\overline{k}\cdot \varDelta _{max}))\) and \(O(\varDelta _{max}/(\overline{k}\cdot m))\), respectively. Where \(\overline{k}\) (\(1<\overline{k}<\varDelta _{max}\)) is a constant called the SNR diversity of an instance G.     

Leadership research and cognitive neuroscience: The state of this union

Advances in cognitive neuroscience and other approaches to understanding human behavior from a biological standpoint are only now beginning to filter into leadership research. The purpose of this introduction to the Leadership Quarterly Special Issue on the Biology of Leadership is to outline the organizational cognitive neuroscience approach to leadership research, and show how such an approach can fruitfully inform both leadership and neuroscientific research. Indeed, we advance the view that the further application of cognitive neuroscientific techniques to leadership research will pay great dividends in our understanding of effective leadership behaviors and as such, a future symbiosis between the two fields is a necessity.     

Internationalization paths of Indian pharmaceutical firms — A strategic group analysis

This paper is an attempt to throw light on the internationalization paths of emerging economy firms through a strategic group analysis of internationalizing firms in the Indian pharmaceutical industry. Strategic group analysis of a proprietary data set of strategic variables from forty firms revealed significant variation in their internationalization strategies. The distinct strategies exhibited different value creation potential, but led to similar levels of performance in terms of return on assets, thus indicating equifinality of different paths to multinationality. Inductively drawing from in-depth analysis of firms from each of the strategic groups, the paper proposes a conceptual model of internationalization for emerging economy firms through a combination of exploitation and exploration strategies along the dimensions of products and markets. Firms that are able to supplement the conventional exploitation strategies with exploration through new products and new markets, by taking advantage of increasingly liberalized economies, could emerge as Third-world multinationals with capabilities that could potentially challenge even MNCs from the developed world.     

Commitment to the union: a survey of research and the implications for industrial relations and trade unions

This paper presents an overview of the literature on union commitment. The aim is to survey the main approaches, findings and implications of the research. The nature and dimensionality of union commitment are examined, and the antecedents and consequences of union commitment are discussed in detail, including a review of the implications for union participation. There is also a discussion of the possibility of dual commitment to union and employer, and of the 'multiple constituencies' view of commitment. An attempt is made to link the union commitment findings to the wider industrial relations literature on, for example, why people join unions and the 'union renewal' thesis. The article concludes by discussing the implications of the literature for union–management relationships and for unions themselves, and with some suggestions for future research.