6050292
Labeling Planar Graphs with Conditions on Girth and Distance Two
For a planar graph $G$, let $\Delta(G)$, $g(G)$, and $\lambda(G;p,q)$ denote, respectively, its maximum degree, girth, and $L(p,q)$-labeling number. We prove that (1) $\lambda(G;p,q)\le (2q-1)\Delta(G)+4p+4q-4$ if $g(G)\ge 7$; (2) $\lambda(G;p,q)\le (2q-1)\Delta(G)+6p+12q-9$ if $g(G)\ge 6$; (3) $\lambda(G;p,q)\le (2q-1)\Delta(G)+6p+24q-15$ if $g(G)\ge 5$. These bounds have consequences on conjectures by Wegner [Graphs with Given Diameter and a Coloring Problem, preprint, University of Dortmund, Dortmund, Germany, 1977] and Griggs and Yeh [SIAM J. Discrete Math., 5 (1992), pp. 586--595].
1003852
Upper Bounds of Entire Chromatic Number of Plane Graphs
The entire chromatic number χvef (G) of a plane graph G is the least number of colors assigned to the vertices, edges and faces so that every two adjacent or incident pair of them receive different colors. Kronk and Mitchem (1973) conjectured that χvef (G) ≤ 1 + 4 for every plane graph G. In this paper we prove the conjecture for a plane graph G having χ ′(G) = 1 and give a upper bound χvef (G) ≤ 1+ 5 for all plane graphs, where χ ′(G) and 1 are the chromatic index and the maximum degree of G, respectively.
9810371
The edge-face choosability of plane graphs
A plane graph G is said to be k-edge-face choosable if, for every list L of colors satisfying |L(x)|=k for every edge and face x, there exists a coloring which assigns to each edge and each face a color from its list so that any adjacent or incident elements receive different colors. We prove that every plane graph G with maximum degree Δ(G) is (Δ(G)+3)-edge-face choosable.
6853966
Total chromatic number of planar graphs with maximum degree ten
26709203
The Linear 2-Arboricity of Outerplanar Graphs
11186519
Edge-partitions of graphs of nonnegative characteristic and their game coloring numbers
Let G be a graph of nonnegative characteristic and let g(G) and @D(G) be its girth and maximum degree, respectively. We show that G has an edge-partition into a forest and a subgraph H so that (1) @D(H)= =11; (2) @D(H)= =7; (3) @D(H)= =5 or G does not contain 4-cycles and 5-cycles; (4) @D(H)= =11; (2) col"g(G)= =7; (3) col"g(G)= =5 or G contains no 4-cycles and 5-cycles; (4) col"g(G)=<10 if G does not contain 4-cycles.
10774024
Accurate Classification of Protein Structural Families Using Coherent Subgraph Analysis
Protein structural annotation and classification is an important problem in bioinformatics. We report on the development of an efficient subgraph mining technique and its application to finding characteristic substructural patterns within protein structural families. In our method, protein structures are represented by graphs where the nodes are residues and the edges connect residues found within certain distance from each other. Application of subgraph mining to proteins is challenging for a number reasons: (1) protein graphs are large and complex, (2) current protein databases are large and continue to grow rapidly, and (3) only a small fraction of the frequent subgraphs among the huge pool of all possible subgraphs could be significant in the context of protein classification. To address these challenges, we have developed an information theoretic model called coherent subgraph mining. From information theory, the entropy of a random variable X measures the information content carried by X and the Mutual Information (MI) between two random variables X and Y measures the correlation between X and Y. We define a subgraph X as coherent if it is strongly correlated with every sufficiently large sub-subgraph Y embedded in it. Based on the MI metric, we have designed a search scheme that only reports coherent subgraphs. To determine the significance of coherent protein subgraphs, we have conducted an experimental study in which all coherent subgraphs were identified in several protein structural families annotated in the SCOP database (Murzin et al, 1995). The Support Vector Machine algorithm was used to classify proteins from different families under the binary classification scheme. We find that this approach identifies spatial motifs unique to individual SCOP families and affords excellent discrimination between families.
14611333
TAR: temporal association rules on evolving numerical attributes
Data mining has been an area of increasing interest. The association rule discovery problem in particular has been widely studied. However, there are still some unresolved problems. For example, research on mining patterns in the evolution of numerical attributes is still lacking. This is both a challenging problem and one with significant practical applications in business, science, and medicine. In this paper we present a temporal association rule model for evolving numerical attributes. Metrics for qualifying a temporal association rule include the familiar measures of support and strength used in traditional association rule mining and a new metric called density. The density metric not only gives us a way to extract the rules that best represent the data, but also provides an effective mechanism to prune the search space. An efficient algorithm is devised for mining temporal association rules, which utilizes all three thresholds (especially the strength) to prune the search space drastically. Moreover, the resulting rules are represented in a concise manner via rule sets to reduce the output size. Experimental results on real and synthetic data sets demonstrate the efficiency of our algorithm.
14320982
Sequential Pattern Mining in Multi-Databases via Multiple Alignment
To efficiently find global patterns from a multi-database, information in each local database must first be mined and summarized at the local level. Then only the summarized information is forwarded to the global mining process. However, conventional sequential pattern mining methods based on support cannot summarize the local information and is ineffective for global pattern mining from multiple data sources. In this paper, we present an alternative local mining approach for finding sequential patterns in the local databases of a multi-database. We propose the theme of approximate sequential pattern mining roughly defined as identifying patterns approximately shared by many sequences. Approximate sequential patterns can effectively summerize and represent the local databases by identifying the underlying trends in the data. We present a novel algorithm, ApproxMAP, to mine approximate sequential patterns, called consensus patterns, from large sequence databases in two steps. First, sequences are clustered by similarity. Then, consensus patterns are mined directly from each cluster through multiple alignment. We conduct an extensive and systematic performance study over synthetic and real data. The results demonstrate that ApproxMAP is effective and scalable in mining large sequences databases with long patterns. Hence, ApproxMAP can efficiently summarize a local database and reduce the cost for global mining. Furthremore, we present an elegant and uniform model to identify both high vote sequential patterns and exceptional sequential patterns from the collection of these consensus patterns from each local databases.
83220
Defending against wormhole attacks in mobile ad hoc networks
In ad hoc networks, malicious nodes can deploy wormhole attacks to fabricate a false scenario on the proximity relationship among mobile nodes. A classification of the attacks according to the format of the wormholes is proposed. This forms a basis to identify the detection capability of various approaches. An analysis shows that earlier approaches focus on the prevention of wormholes among neighbors that trust each other. As a more generic approach, we present an end-to-end scheme that can detect wormholes on a multi-hop route. Only the trust between the source and the destination is assumed. The mechanism uses geographic information to detect anomalies in neighbor relations and node movements. To reduce the computation and storage overhead, we present a scheme called cell-based open tunnel avoidance (COTA) to manage the information. COTA requires a constant space for every node on the path and the computation overhead increases linearly to the number of detection packets. We prove that the savings do not deteriorate the detection capability. Various schemes to control communication overhead are studied. The simulation and experiments on real devices show that the proposed mechanism can be combined with existent routing protocols to defend against wormhole attacks. Copyright © 2006 John Wiley & Sons, Ltd.
11994567
Enhancing Levin's method for computing quadric-surface intersections
Levin's method produces a parameterization of the intersection curve of two quadrics in the form p(u) = a(u) ± d(u) √s(u), where a(u) and d(u) are vector valued polynomials, and s(u) is a quartic polynomial. This method, however, is incapable of classifying the morphology of the intersection curve, in terms of reducibility, singularity, and the number of connected components, which is critical structural information required by solid modeling applications. We study the theoretical foundation of Levin's method, as well as the parameterization p(u) it produces. The following contributions are presented in this paper: (1) It is shown how the roots of s(u) can be used to classify the morphology of an irreducible intersection curve of two quadric surfaces. (2) An enhanced version of Levin's method is proposed that, besides classifying the morphology of the intersection curve of two quadrics, produces a rational parameterization of the curve if the curve is singular. (3) A simple geometric proof is given for the existence of a real ruled quadric in any quadric pencil, which is the key result on which Levin's method is based. These results enhance the capability of Levin's method in processing the intersection curve of two general quadrics within its own self-contained framework.