12158249
Bisingular maps on the sphere and the projective plane
Abstract A map is bisingular if each edge is either a loop or an isthmus (i.e., on the boundary of the same face). In this paper we study the number of rooted bisingular maps on the plane or projective plane and also we present formulae for such maps with up to three or more parameters: the root valency, the number of isthmus, the number of essential loops, and the number of planar loops.
43124802
On the Isomorphisms of Cayley Graphs of Abelian Groups
Let G be a finite group, S a subset of G\{1}, and let Cay (G, S) denote the Cayley digraph of G with respect to S. If, for any subset T of G\{1}, Cay(G, S) ≅ Cay(G, T) implies that Sα = T for some α ∈ Aut(G), then S is called a CI-subset. The group G is called a CIM-group if for any minimal generating subset S of G, S ∪ S-1 is a CI-subset. In this paper, CIM-abelian groups are characterized.
43519756
The Number of Loopless 4-Regular Maps on the Projective Plane
In this paper rooted loopless (near) 4-regular maps on surfaces such as the sphere and the projective plane are counted and exact formulae with up to three or four parameters for such maps are given. Several classical results on regular maps and one-faced maps are deduced.
36739594
Generating cycle spaces for graphs on surfaces with small genera
In this paper we investigate cycle base structures of a 2-(edge)-connected graph on surfaces with small genera and show that short cycles do generate the cycle spaces in the case of "small face-embeddings". Examples show that the conditions in our main results are best possible. As applications we find the exact formulae for the minimum lengths of cycle bases of some types of graphs which conclude several known results. Finally, we generalize those results for graphs embedded on general orientable surfaces.
39617215
Counting rooted near-triangulations on the sphere
This paper provides the results on the enumerations of rooted simple outerplanar maps, rooted outerplanar near-triangulations, rooted 2-connected near-triangulations, rooted strict 2-connected near-triangulations and rooted simple 2-connected near-triangulations. The answer to an open problem proposed by one of the authors is also provided.
44495329
Enumeration on Nonseparable Planar Maps
Abstract This paper provides some functional equations satisfied by the generating functions for nonseparable rooted planar maps with the valency of root-vertex, the number of edges and the valency of root-faces of the maps as three parameters. But the solutions of these equations can only be obtained indirectly by considering some relations between nonseparable and general rooted planar maps. One of them is an answer to the open problem 6.1 in Liu (1983, Comb. Optim. CORR83-26, University of Waterloo).
205876923
Number of maximum matchings of bipartite graphs with positive surplus
A bipartite graph G=(A,B) is said to have positive surplus (as viewed from A) if the number of neighbors of X is bigger than the size of X for any non-empty subset X of A. In this paper, two lower bounds on the number of maximum matchings in bipartite graphs with positive surplus are obtained. The enumeration problems for maximum matchings in special bipartite graphs are solved. From this, the number of perfect matchings of some elementary bipartite graphs is given.
43698695
The fractional matching numbers of graphs
A fractional matching of a graph G is a function f that assigns to each edge a number in [0, 1] such that, for each vertex v, ∑ f(e) ≤ 1, where the sum is taken over all edges incident to v. The fractional matching number of G is the supremum of ∑e∈E(G)f(e) over all fractional matchings f. In this paper, we provide a new formula for calculating the fractional matching numbers of graphs using the Gallai–Edmonds Structure Theorem. Thus, we characterize graphs for which the fractional matching number equals the matching number and graphs for which the fractional matching number is the maximum possible (one-half the number of vertices). © 2002 Wiley Periodicals, Inc.
1753568
Learning multispectral texture features for cervical cancer detection
We present a bottom-up approach for automatic cancer cell detection in multispectral microscopic thin Pap smear images. Around 4,000 multispectral texture features are explored for cancer cell detection. Using two feature screening measures, the initial feature set is effectively reduced to a computationally manageable size. Based on pixel-level screening results, cancerous regions can thus be detected through a relatively simple procedure. Our experiments have demonstrated the potential of both multispectral and texture information to serve as valuable complementary cues to traditional detection methods.
132343
Approaching optimal peer-to-peer overlays
In unstructured peer-to-peer (P2P) systems, there exists a serious topology mismatch problem between physical and logical network. We first analyze the relationship between the property of the overlay and the corresponding message duplications incurred by queries in a given overlay, and prove that computing an optimal overlay with global knowledge is an NP-hard problem. Motivated by the analysis results, we design a distributed overlay optimization algorithm, THANCS, to attack topology mismatch. We demonstrate its performance by comprehensive simulations in dynamic environments. The proposed THANCS has three major strengths. First, it does not need any global knowledge. Second, its optimization convergent speed is fast. Third, it is orthogonal with other types of advanced search approaches.
10483406
A maximum coherence model for dictionary-based cross-language information retrieval
One key to cross-language information retrieval is how to efficiently resolve the translation ambiguity of queries given their short length. This problem is even more challenging when only bilingual dictionaries are available, which is the focus of this paper. In the previous research of cross-language information retrieval using bilingual dictionaries, the word co-occurrence statistics is used to determine the most likely translations of queries. In this paper, we propose a novel statistical model, named ``maximum coherence model'', which estimates the translation probabilities of query words that are consistent with the word co-occurrence statistics. Unlike the previous work, where a binary decision is made for the selection of translations, the new model maintains the uncertainty in translating query words when their sense ambiguity is difficult to resolve. Furthermore, this new model is able to estimate translations of multiple query words simultaneously. This is in contrast to many previous approaches where translations of individual query words are determined independently. Empirical studies with TREC datasets have shown that the maximum coherence model achieves a relative 10% - 40% improvement in cross-language information retrieval, comparing to other approaches that also use word co-occurrence statistics for sense disambiguation.