5533376
Characterizations of maximum matching graphs of certain types
The maximum matching graph M(G) of a graph G is a graph whose vertices are maximum matchings of G and where two maximum matchings are adjacent in M(G) if they differ in exactly one edge. In this paper, the author characterizes the graphs whose maximum matching graphs are regular or cycles, and adds trees to the list of known maximum matching graphs.
34451404
The enumeration of near-perfect matchings of factor-critical graphs
Abstract A matching of a graph is a near-perfect matching if it covers all but one vertex. A connected graph G is said to be factor-critical if G − v has perfect matchings for every vertex v of G. In this paper, the enumeration problems for near-perfect matchings in special factor-critical graphs are solved. From this, the exact values of the number of perfect matchings in special bicritical graphs are obtained.
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.
12595607
Sketch Recognition Based on Topological Spatial Relationship
In recognition of composite graphic objects, topological spatial relationships of their components play an important role. Although most researchers focus on binary topological relationships, they cannot carry all information of the internal structure of the compound objects. Therefore, we introduce the ternary relationship, which is a complement to the binary relationship, to describe composite graphic objects. Moreover, we provide a constrained partial permutation algorithm based on both the binary and ternary topological spatial relationships to recognize the sketchy objects input by users in an online manner. Experimental results show that this approach is both efficient and effective for online composite graphics recognition in our sketch-based graphics input system–SmartSketchpad.
1236601
Skewed symmetry groups
We introduce the term skewed symmetry groups and provide a complete theoretical treatment for 2D wallpaper groups under affine transformations. For the first time, a given periodic pattern can be classified not simply by its Euclidean symmetry group but,by its highest "potential" symmetry group under affine deformation. A concise wallpaper group migration map is constructed that separates the 17 affinely deformed wallpaper groups into small, distinct orbits. The practical value of this result includes a novel indexing and retrieval scheme for regular patterns, and a maximal-symmetry-based method for estimating shape and orientation from texture under unknown views.
5050501
Eliminating dead code on recursive data
This paper describes a powerful method for dead-code analysis and elimination in the presence of recursive data constructions. We describe partially dead recursive data using liveness patterns based on general regular tree grammars extended with the notion of live and dead, and we formulate the analysis as computing liveness patterns at all program points based on constraints constructed from the program and programming language semantics. The analysis yields the most precise program-based grammars that satisfy the constraints. The analysis algorithm takes cubic time in terms of the size of the program in the worst case but is very efficient in practice, as shown by our prototype implementation. The analysis results are used to identify and eliminate dead code. The framework for representing and analyzing properties of recursive data structures using general regular tree grammars applies to other analyses as well.
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.