A constrained partial permutation strategy is proposed for matching spatial relation graph (SRG), which is used in our sketch input and recognition system Smart Sketchpad for representing the spatial relationship amon...A constrained partial permutation strategy is proposed for matching spatial relation graph (SRG), which is used in our sketch input and recognition system Smart Sketchpad for representing the spatial relationship among the components of a graphic object. Using two kinds of matching constraints dynamically generated in the matching process, the proposed approach can prune most improper mappings between SRGs during the matching process. According to our theoretical analysis in this paper, the time complexity of our approach is O(n 2) in the best case, and O(n!) in the worst case, which occurs infrequently. The spatial complexity is always O(n) for all cases. Implemented in Smart Sketchpad, our proposed strategy is of good performance.展开更多
This paper is concerned with the enumeration of a special kind of labeled connected graphs of which the cutpoint-graphs are trees.A new method—treelization is introduced, by which the enumeration of this special kind...This paper is concerned with the enumeration of a special kind of labeled connected graphs of which the cutpoint-graphs are trees.A new method—treelization is introduced, by which the enumeration of this special kind of graphs can be solved. The enumerative formula with generating function is derived. The method of treelization is powerful in solving enumeration problems of graphs and deserves further research. For example, using the similar way, another special kind of labeled connected graphs of which the block-graphs are trees can be enumerated.展开更多
文摘A constrained partial permutation strategy is proposed for matching spatial relation graph (SRG), which is used in our sketch input and recognition system Smart Sketchpad for representing the spatial relationship among the components of a graphic object. Using two kinds of matching constraints dynamically generated in the matching process, the proposed approach can prune most improper mappings between SRGs during the matching process. According to our theoretical analysis in this paper, the time complexity of our approach is O(n 2) in the best case, and O(n!) in the worst case, which occurs infrequently. The spatial complexity is always O(n) for all cases. Implemented in Smart Sketchpad, our proposed strategy is of good performance.
文摘This paper is concerned with the enumeration of a special kind of labeled connected graphs of which the cutpoint-graphs are trees.A new method—treelization is introduced, by which the enumeration of this special kind of graphs can be solved. The enumerative formula with generating function is derived. The method of treelization is powerful in solving enumeration problems of graphs and deserves further research. For example, using the similar way, another special kind of labeled connected graphs of which the block-graphs are trees can be enumerated.