A tree $t$-spanner $T$ of a simple graph $G$ is a spanning tree of $G$, such that for every pair of vertices of $G$ their distance in $T$ is at most $t$ times their distance in $G$, where $t$ is called a stretch factor of $T$ in $G$. It has been shown that there is a linear time algorithm to find a tree 2-spanner in a graph; it has also been proved that, for each $t>3$, determining whether a graph admits a tree $t$-spanner is an NP-complete problem. This thesis studies tree $t$-spanners from both theoretical and algorithmic perspectives. In particular, it is proved that a nontree graph admits a unique tree $t$-spanner for at most one value of stretch factor $t$. As a corollary, a nontree bipartite graph cannot admit a unique tree $t$-spanner for any $t$. But, for each $t$, there are infinitely many nontree graphs that admit exactly one tree $t$-spanner. Furthermore, for each $t$, let U($t$) be the set of graphs being the union of two tree $t$-spanners of a graph. Although graphs in U(2) do not have cycles of length greater than 4, graphs in U(3) may contain cycles of arbitrary length. It turns out that any even cycle is an induced subgraph of a graph in U(3), while no graph in U(3) contains an induced odd cycle other than a triangle; graphs in U(3) are shown to be perfect. Also, properties of induced even cycles of graphs in U(3) are presented. For each $t>3$, though, graphs in U($t$) may contain induced odd cycles of any length. Moreover, there is an efficient algorithm to recognize graphs that admit a tree 3-spanner of diameter at most 4, while it is proved that, for each $t>3$, determining whether a graph admits a tree $t$-spanner of diameter at most $t+1$ is an NP-complete problem. It is not known if it is hard to recognize graphs that admit a tree 3-spanner of general diameter; however integer programming is employed to provide certificates of tree 3-spanner inadmissibility for a family of graphs.

A tree $t$-spanner $T$ of a simple graph $G$ is a spanning tree of $G$, such that for every pair of vertices of $G$ their distance in $T$ is at most $t$ times their distance in $G$, where $t$ is called a stretch factor of $T$ in $G$. It has been shown that there is a linear time algorithm to find a tree 2-spanner in a graph; it has also been proved that, for each $t>3$, determining whether a graph admits a tree $t$-spanner is an NP-complete problem. This thesis studies tree $t$-spanners from both theoretical and algorithmic perspectives. In particular, it is proved that a nontree graph admits a unique tree $t$-spanner for at most one value of stretch factor $t$. As a corollary, a nontree bipartite graph cannot admit a unique tree $t$-spanner for any $t$. But, for each $t$, there are infinitely many nontree graphs that admit exactly one tree $t$-spanner. Furthermore, for each $t$, let U($t$) be the set of graphs being the union of two tree $t$-spanners of a graph. Although graphs in U(2) do not have cycles of length greater than 4, graphs in U(3) may contain cycles of arbitrary length. It turns out that any even cycle is an induced subgraph of a graph in U(3), while no graph in U(3) contains an induced odd cycle other than a triangle; graphs in U(3) are shown to be perfect. Also, properties of induced even cycles of graphs in U(3) are presented. For each $t>3$, though, graphs in U($t$) may contain induced odd cycles of any length. Moreover, there is an efficient algorithm to recognize graphs that admit a tree 3-spanner of diameter at most 4, while it is proved that, for each $t>3$, determining whether a graph admits a tree $t$-spanner of diameter at most $t+1$ is an NP-complete problem. It is not known if it is hard to recognize graphs that admit a tree 3-spanner of general diameter; however integer programming is employed to provide certificates of tree 3-spanner inadmissibility for a family of graphs.

This study is motivated by a desire to understand the role of boundary spanners in creating satisfactory alliance. Specifically, the relationships between organizational culture, boundary spanner, and alliance performance were examined. In general, results from an empirical investigation with 116 alliance experiences supported the notion that alliance partners with higher similarity of organizational culture perceived higher alliance performance. By the same token, higher capabilities of boundary spanners lead to higher alliance performance. Furthermore, the relationships between the organizational culture and alliance performance were mediated through their boundary spanners¡¦ capability.

ABSTRACT ¡@¡@With the global economic change and rising pressure of market competition, product-oriented business trend changed into customer-oriented gradually. It becomes an important task about how to enhance the competitiveness of enterprises, response the requirement from customer, and making better interaction with customer. Therefore, the role of boundary spanner has become more and more important for organization. The past research of boundary spanner almost focus on the quantitative research method of personal managerial skills of boundary spanner, validity and verification for boundary spanner personal scale and the performance between boundary spanner and organization. This research adopts the narrative method, taking customer service engineer as example, Start from the borders of boundary spanner, hoping to provide another observation of boundary spanner. The result of research indicates that there are four features of the work of boundary spanner : Practice bring efficient learning, Situated learning lead adaptive behavior, Low profile adapt role conflict and adaptive behavior is negative to continued learning and challenge the management of company. Hope these results could be the reference of academic continued research and company training. Also hope these result could be the inspiration of other customer service engineer and encourage them to make more contributation on their job.

University, Diss., 2002--Bayreuth. / Erscheinungsjahr an der Haupttitelstelle: 2002.

The well-separated pair decomposition (WSPD) of the complete Euclidean graph defined on points in R 2 , introduced by Callahan and Kosaraju [JACM, 42 (1): 67-90, 1995], is a technique for partitioning the edges of the complete graph based on length into a linear number of sets. Among the many different applications of WSPDs, Callahan and Kosaraju proved that the sparse subgraph that results by selecting an arbitrary edge from each set (called WSPD-spanner) is a 1 + 8/(s − 4)-spanner, where s > 4 is the separation ratio used for partitioning the edges. Although competitive local-routing strategies exist for various spanners such as Yao-graphs, Θ-graphs, and variants of Delaunay graphs, few local-routing strategies are known for any WSPD-spanner. Our main contribution is a local-routing algorithm with a near-optimal competitive routing ratio of 1 + O(1/s) on a WSPD-spanner. Specifically, using Callahan and Kosaraju’s fair split-tree, we show how to build a WSPD-spanner with spanning ratio 1 + 4/s + 4/(s − 2) which is a slight improvement over 1 + 8/(s − 4). We then present a 2-local and a 1-local routing algorithm on this spanner with competitive routing ratios of 1 + 6/(s − 2) + 4/s and 1 + 8/(s − 2) + 4/s + 8/s 2 , respectively. Moreover, we prove that there exists a point set for which our WSPD-spanner has a spanning ratio of at least 1 + 8/s, thereby proving the near-optimality of its spanning ratio and the near-optimality of the routing ratio of both our routing algorithms.

Finding the exact spanning ratio of a Delaunay graph has been one of the longstanding open problems in Computational Geometry. Currently there are only four convex shapes for which the exact spanning ratio of their Delaunay graph is known: the equilateral triangle, the square, the regular hexagon and the rectangle. In this paper, we show the exact spanning ratio of the parallelogram Delaunay graph, making the parallelogram the fifth convex shape for which an exact bound is known. The worst-case spanning ratio is exactly $$\frac{\sqrt{2}\sqrt{1+A^2+2A\cos(\theta_0)+(A+\cos(\theta_0))\sqrt{1+A^2+2A\cos(\theta_0)}}}{\sin(\theta_0)},$$ where A is the aspect ratio and θ_0 is the non-obtuse angle of the parallelogram. Moreover, we show how to construct a parallelogram Delaunay graph whose spanning ratio matches the above mentioned spanning ratio.

Seja (G,w,t) uma tripla formada por um grafo conexo G = (V,E), uma função peso não-negativa w definida em E e um número real t >= 1, chamado de fator de dilatação. Um t-spanner de G é um subgrafo gerador H de G tal que para cada par de vértices u, v, a distância entre u e v em H é no máximo t vezes a distância entre u e v em G. Quando H é uma árvore, dizemos que H é uma árvore t-spanner. Nesta tese focamos o problema da árvore t- spanner de peso mínimo (cuja sigla em inglês é MWTSP), definido a seguir. Dada uma tripla (G,w,t), encontrar uma árvore t-spanner em G de peso mínimo. É sabido que MWTSP é NP-difícil para cada t > 1 fixo. Propomos duas formulações lineares inteiras para MWTSP, baseadas em arborescência, de tamanho polinomial no tamanho de G. A formulação que possui variáveis representando distâncias entres os pares de vértices apresentou resultados melhores na prática. Também abordamos o problema de t-spanner de peso mínimo (cuja sigla em inglês é MWSP), cuja entrada é a mesma do MWTSP e cujo objetivo é encontrar um t-spanner de peso mínimo. Mesmo para grafos com peso unitário, MWSP é NP-difícil para cada t >= 2 fixo. Tratamos este problema de duas formas. Propomos uma formulação linear inteira para o MWSP que possui um número exponencial de restrições, mas cujo problema da separação para o programa linear relaxado correspondente é polinomial no tamanho de G. Apresentamos também uma implementação de um algoritmo de branch-and-price para o MWSP baseado numa formulação linear inteira proposta por Sigurd e Zachariasen (2004). Exibimos resultados de experimentos realizados com as duas formulações para o MWTSP e também com o algoritmo de branch-and-price para o MWSP. / Let (G, w, t) be a triplet consisting of a connected graph G = (V, E) with a nonnegative weight function w defined on E, and a real number t >= 1. A t-spanner of G is a spanning subgraph H of G such that for each pair of vertices u,v, the distance between u and v in H is at most t times the distance between u and v in G. If H is a tree then we call it a tree t-spanner of G. We address the Minimum Weight Tree Spanner Problem (MWTSP), defined as follows. Given a triplet (G, w, t), find a minimum weight tree t-spanner in G. It is known that MWTSP is NP-hard for every fixed t > 1. We propose two ILP formulations for MWTSP, based on arborescences, of polynomial size in the size of G. The formulation that has variables representing distances between pairs of vertices has shown to be better in practice. We also address the Minimum Weight t-Spanner Problem (MWSP) that has the same input as MWTSP and seeks for a minimum weight t-spanner in G. Even for unweighted graphs, it is known that MWSP is NP-hard for every fixed t >= 2. We approach this problem in two ways. We propose an ILP formulation for MWSP that has an an exponential number of restrictions but we show that the separation problem for the corresponding relaxed linear program can be solved in polynomial time in the size of G. We also present a branch-and-price algorithm for MWSP based on an ILP formulation proposed by Sigurd and Zachariasen (2004). We show results on the computational experiments with both formulations for MWTSP and also with the branch-and-price algorithm that we implemented for MWSP.

Interfirm collaboration has long been deemed as a fast strategy to obtain organizational competitiveness. The ability of organizations to obtain information from and disseminate knowledge signifies the importance of whether a firm can achieve knowledge creation among the networked firms and firms therefore can gain competitive advantages. The research was conducted using a qualitative approach; case details were collected from firms involving international strategic alliance. The research aims to investigate the influences of boundary spanners, information technology and corporate cultures on organizational competitiveness in strategic alliances. Findings reveal that boundary spanners, cultural issues and information technology are positively related to organizational competitiveness.

A t-spanner of a graph G is a subgraph H of G, which the distance between any two vertices in H is at most t times their distance in G. A tree t-spanner of G is a t-spanner which is a tree. In this dissertation, we discuss the t-spanners on trapezoid, permutation, and interval graphs. We first introduce an O(n) algorithm for finding a tree 4-spanner on trapezoid graphs. Then, give an O(n)algorithm for finding a tree 3-spanner on permutation graphs, improving the existed O(n + m) algorithm. Since the class of permutation graphs is a subclass of trapezoid graphs, we can apply the algorithm on permutation graphs to find the approximation of a tree 3-spanner on trapezoid graphs in O(n) time with edge bound 2n. Finally, we show that not all interval graphs have a tree 2-spanner.