26138426
2-diameter of de Bruijn graphs
Binary strings are used as vertex labels or components of vertex labels. We will abbreviate “the vertex with label X” as “vertex x.” The binarji direcred de Briiijn graph of dimension n , denoted B ( n ) , has 2 ” vertices which are labeled with the binary strings of length n . There is an arc from any vertex x, x2 xn to the vertices x2x3 x,O and x2x3 x,, 1. We say that the ith coordinate of ,Y is x, . Any .u, is equal toOor l , andZ, = 1 x i . The undirected binary de Bruijn graph UB( n ) is obtained from B( n) by deleting the orientation of the arcs and omitting multiple edges and loops. It is well known that UB( n ) is 2-connected and that its diameter (maximum of the distances between all pairs of vertices) is equal to n . Due to their bounded maximum degree equal to 4 and their low diameter, de Bruijn graphs have been proposed as a possible good interconnection network for a parallel architecture [ 11. They have also been shown to solve a wide class of problems [ 21. For a k-connected graph, Hsu [ 4 ] introduced the notion of the kdiameter as follows: Given any two vertices x and y , a k-container between x and y is a set of k vertex disjoint paths between xand y . The length ofa k-container is the length of the longest of the k paths. The kdistance d k ( x , y ) between x and y is the minimum of the lengths of all the k-containers. Then, the k-diameter of a graph G is the maximum of d k ( x , y) for all pairs of vertices x and y . General results on the k-diameters of k-regular kconnected graphs can be found in [ 41 or [ 51. Results for some particular classes ofgraphs and many open problems can also be found in [ 41. It was shown by Pradhan and Reddy [ 7 ] that the 2diameter of U B ( n ) is less than or equal to 2n. The 2diameter is also obviously at least n. The aim of this paper was to prove that it is exactly n. In other words, between any two vertices of UB( n ) , there exist two internally vertex disjoint paths of length at most n. This gives a good measure of the fault tolerance of the graph [ 61. Let us first introduce some notation and recall some properties of the de Bruijn digraph B( n ) : Given two vertices x and y , we will denote f i x , y ] as a shortest path P from x to y . The length of this path, denoted by I PIX, y ] 1, is the number of edges in the path and is also the distance d ( x , y ) from x to y . P [ x , y ] also represents the set of vertices of the path, including its extremities.
15417765
The proof of a conjecture of Bouabdallah and Sotteau
Let G be a connected graph of order n. A routing in G is a set of n(n 1) fixed paths for all ordered pairs of vertices of G. The edge-forwarding index of G, (G), is the minimum of the maximum number of paths specified by a routing passing through any edge of G taken over all routings in G, and ,n is the minimum of (G) taken over all graphs of order n with maximum degree at most . To determine n 2p 1,n for 4p 2p/3 1 ≤ n ≤ 6p, A. Bouabdallah and D. Sotteau proposed the following conjecture in [On the edge forwarding index problem for small graphs, Networks 23 (1993), 249–255]. The set 3 {1, 2, . . . , (4p)/3} can be partitioned into 2p pairs plus singletons such that the set of differences of the pairs is the set 2 {1, 2, . . . , p}. This article gives a proof of this conjecture and determines that n 2p 1,n is equal to 5 if 4p 2p/3 1 ≤ n ≤ 6p and to 8 if 3p p/3 1 ≤ n ≤ 3p (3p)/5 for any p ≥ 2. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(4), 292–296 2004
15426263
Super connectivity of line graphs
The super connectivity κ' and the super edge-connectivity λ' are more refined network reliability indices than connectivity κ and edge-connectivity λ. This paper shows that for a connected graph G with order at least four rather than a star and its line graph L(G), κ'(L(G)) = λ'(G) if and only if G is not super-λ'. As a consequence, we obtain the result of Hellwig et al. [Note on the connectivity of line graphs, Inform. Process. Lett. 91 (2004) 7] that κ(L(G)) = λ'(G). Furthermore, the authors show that the line graph of a super-λ' graph is super-λ if the minimum degree is at least three.
872168
The super connectivity of shuffle-cubes
The shuffle-cube SQn, where n ≡ 2 (mod 4), a new variation of hypercubes proposed by Li et al. [T.-K. Li, J.J.M. Tan, L.-H. Hsu, T.-Y. Sung, The shuffle-cubes and their generalization, Inform. Process. Lett. 77 (2001) 35-41], is an n-regular n-connected graph. This paper determines that the super connectivity of SQn is 2n - 4 and the super edge-connectivity is 2n - 2 for n ≥ 6.
7639532
Fault diameter of Cartesian product graphs
The (k-1)-fault diameter D"k(G) of a k-connected graph G is the maximum diameter of G-F for any F@?V(G) with |F|=1 for i=1,2.
39336188
Local Strongly Arc-Connectivity in Regular Bipartite Digraphs
We show that for any vertex x of a d-regular bipartite digraph there are a vertex y, in the other class of the bipartition, and d (x, y)-paths and d (y, x)-paths such that all 2d of them are pairwise arc-disjoint. This result generalizes a theorem of Hamidoune and Las Vergnas for graphs.
5147011
Wide Diameters of Cartesian Product Graphs and Digraphs
In graph theory and study of fault tolerance and transmission delay of networks, connectivity and diameter of a graph are two very important parameters and have been deeply studied by many authors. Wide diameter combining connectivity with diameter is a more important parameter to measure fault tolerance and efficiency of parallel processing computer networks and has received much attention in the recent years. Diameter with width k of a graph G is defined as the minimum integer d for which between any two distinct vertices in G there exist at least k internally disjoint paths of length at most d. In the present paper, the tight upper bounds of wide diameter of the Cartesian product graphs are obtained. Some known results can be deduced or improved from ours.
12382521
On the design and performance of prefix-preserving IP traffic trace anonymization
Even though real-world Internet traffic traces are crucial for network research, only a tiny percentage of traffic traces collected are made public. One major reason why traffic trace owners hesitate to make the traces publicly available is the concern that the confidential and private information may be inferred from the trace. In this paper we focus on the problem of anonymizing IP addresses in a trace. More specifically, we are interested in prefixpreserving anonymization in which the prefix relationship among IP addresses is preserved in the anonymized trace, making such a trace usable in situations where such prefix relationships are important. The goal of our work is two fold. First, we are interested in analyzing the security properties inherent in prefix-preserving IP address anonymization. Through the analysis of IP traffic traces, we investigate the effect of some types of attacks on the security of the prefix-preserving anonymization process. We also derive results for the optimum manner in which an attack should proceed which provides a bound on the performance of attacks in general. Second, we observe that an existing scheme used for prefix-preserving anonymization, TCPdpriv, has some drawbacks that limit its use in a large-scale, distributed setting. We develop an alternative cryptography-based, prefixpreserving anonymization technique to address these drawbacks while maintaining the same level of anonymity as TCPdpriv.
6867693
Searching Documents Based on Relevance and Type
This paper extends previous work on document retrieval and document type classification, addressing the problem of 'typed search'. Specifically, given a query and a designated document type, the search system retrieves and ranks documents not only based on the relevance to the query, but also based on the likelihood of being the designated document type. The paper formalizes the problem in a general framework consisting of 'relevance model' and 'type model'. The relevance model indicates whether or not a document is relevant to a query. The type model indicates whether or not a document belongs to the designated document type. We consider three methods for combing the models: linear combination of scores, thresholding on the type score, and a hybrid of the previous two methods. We take course page search and instruction document search as examples and have conducted a series of experiments. Experimental results show our proposed approaches can significantly outperform the baseline methods.
16304396
Criminal network analysis and visualization
A new generation of data mining tools and applications work to unearth hidden patterns in large volumes of crime data.
6305531
Shortest path queries in planar graphs
The problem of processing shortest pa th queries in graphs arises in application areas such as intelligent t ranspor ta t ion system (ITS), geographic information system (GIS), and robotics. In this paper, we present an efficient algorithmic solution for processing shortest pa th queries in undirected planar graphs with non-negative edge weights. Previous algorithms for this problem on planar graphs all have a tradeoff between the query t ime and the da ta structure space used by the solutions. The previously best known trade-off on an n-vertex planar graph G in the worst case is O(v/-r) t ime for a pa th length query and O(v/-r + L) t ime for report ing an actual shortest path, with a da ta structure of O(n2/x/~) space, where r is an integer parameter with 1 < r _< n and L is the number of edges on the output shortest path. We present a new scheme, called frame search, that exploits the graph planari ty in a novel fashion. Wi th this scheme, we build an improved da ta structure of O(n + pv/-r + p2/r) space (in O(n + p2/v/~ + pr 3/4) time), where p is the minimum cardinality of a face-covering of the planar embedding of G with 1 < p < O(n), and r is an integer parameter with 1 < r < p. This da ta structure enables us to process each length query in O(v/-rlog r + a(n)) t ime and report an actual shortest path in an addit ional O(L) time, where a(n) is the inverse of Ackermann's function. In the worst case, our approach reduces the previously best query t ime by a factor of up to O(n 1/4) if the same amount of space is used. Our technique can also be applied to improve the previous query algorithms for some geometric shortest pa th problems on the plane.