9332288
Choosability, Edge Choosability, and Total Choosability of Outerplane Graphs
Let ?l(G),?l? (G),?l?? (G), and ?(G) denote, respectively, the list chromatic number, the list chromatic index, the list total chromatic number, and the maximum degree of a non-trivial connected outerplane graph G. We prove the following results. (1) 2 ??l(G) ? 3 and?l (G) = 2 if and only if G is bipartite with at most one cycle. (2)?(G) ??l?(G) ??(G) + 1 and?l? (G) =?(G) + 1 if and only if G is an odd cycle. This proves the well-known list edge coloring conjecture for outerplane graphs. (3)?l??(G) =?(G) + 1 if ?(G) ? 4 and ?l??(G) ? 5 if ?(G) ? 3. This proves a conjecture of O. V. Borodin, A. V. Kostochka and D. R. Woodall, List edge and list total coloring of multigraphs, J. Comb. Theory B, 71 (1997), 184?204 for outerplane 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.
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.
6853966
Total chromatic number of planar graphs with maximum degree ten
26709203
The Linear 2-Arboricity of Outerplanar Graphs
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.
5616933
Techniques for effective vocabulary selection
The vocabulary of a continuous speech recognition (CSR) system is a significant factor in determining its performance. In this paper, we present three principled approaches to select the target vocabulary for a particular domain by trading off between the target out-of-vocabulary (OOV) rate and vocabulary size. We evaluate these approaches against an ad-hoc baseline strategy. Results are presented in the form of OOV rate graphs plotted against increasing vocabulary size for each technique.
377228
SPIN: mining maximal frequent subgraphs from graph databases
One fundamental challenge for mining recurring subgraphs from semi-structured data sets is the overwhelming abundance of such patterns. In large graph databases, the total number of frequent subgraphs can become too large to allow a full enumeration using reasonable computational resources. In this paper, we propose a new algorithm that mines only maximal frequent subgraphs, i.e. subgraphs that are not a part of any other frequent subgraphs. This may exponentially decrease the size of the output set in the best case; in our experiments on practical data sets, mining maximal frequent subgraphs reduces the total number of mined patterns by two to three orders of magnitude.Our method first mines all frequent trees from a general graph database and then reconstructs all maximal subgraphs from the mined trees. Using two chemical structure benchmarks and a set of synthetic graph data sets, we demonstrate that, in addition to decreasing the output size, our algorithm can achieve a five-fold speed up over the current state-of-the-art subgraph mining algorithms.
2987996
Mining patterns in long sequential data with noise
Pattern discovery in time series data has been a problem of great importance in many fields, e.g., computational biology, performance analysis, consumer behavior, etc. Recently, considerable amount of research has been carried out in this area. The facts that the input data is typically very large and noises may present in various formats pose great challenge to the mining process. Recently, we have made several new research advances in this area. In this paper, we present some of them. We will survey new models proposed to address different types of noises as well as scalable algorithms developed for efficiently mining patterns under each model.
45794206
Rational Quadratic Parameterizations of Quadrics
Every irreducible quadric in E3 has infinitely many different rational quadratic parameterizations. These parameterizations and the relationships between them are investigated. It is shown that every faithful rational quadratic parameterization of a quadric can be generated by a stereographic projection from a point on the quadric, called the center of projection (COP). Two such parameterizations for the same quadric are related by a rational linear reparameterization if they have the same COP; otherwise they are related by a rational quadratic reparameterization. We also consider unfaithful parameterizations for which, in general, a one-to-one correspondence between points on the surface and parameters in the plane does not exist. It is shown that all unfaithful rational quadratic parameterizations of a properly degenerate quadric can be characterized by a simple canonical form, and there exist no unfaithful rational quadratic parameterizations for a nondegenerate quadric. In addition, given a faithful rational quadratic parameterization of a quadric, a new technique is presented to compute its base points and inversion formula. These results are applied to solve the problems of parameterizing the intersection of two quadrics and reparameterizing a given quadric parameterization with respect to a different COP without implicitization.
11609470
Interpolating Polyhedral Models Using Intrinsic Shape Parameters
Metamorphosis, or morphing, is the gradual transformation of one shape into another. It generally consists of two subproblems: the correspondence problem and the interpolation problem. This paper presents a solution to the interpolation problem of transforming one polyhedral model into another. It is an extension of the intrinsic shape interpolation scheme (T. W. Sederberg, P. Gao, G. Wang and H. Mu, ‘2-D shape blending: an intrinsic solution to the vertex path problem, SIGGRAPH ’93, pp. 15–18.) for 2D polygons. Rather than considering a polyhedron as a set of independent points or faces, our solution treats a polyhedron as a graph representing the interrelations between faces. Intrinsic shape parameters, such as dihedral angles and edge lengths that interrelate the vertices and faces in the two graphs, are used for interpolation. This approach produces more satisfactory results than the linear or cubic curve paths would, and is translation and rotation invariant.  1997 by John Wiley & Sons, Ltd.