检索结果-内蒙古大学图书馆

***: A gesture recognizer developed using data mining

AI EDAM-ARTIFICIAL INTELLIGENCE FOR ENGINEERING DESIGN ANALYSIS AND MANUFACTURING 2012年第3期26卷 351-366页

作者： Chang, Samuel Hsiao-Heng Blagojevic, Rachel Plimmer, Beryl Univ Auckland Dept Comp Sci Auckland 1142 New Zealand

Although many approaches to digital ink recognition have been proposed, most lack the flexibility and adaptability to provide acceptable recognition rates across a variety of problem spaces. This project uses a systematic approach of data mining analysis to build a gesture recognizer for sketched diagrams. A wide range of algorithms was tested, and those with the best performance were chosen for further tuning and analysis. Our resulting recognizer, RATA. Gesture, is an ensemble of four algorithms. We evaluated it against four popular gesture recognizers with three data sets;one of our own and two from other projects. Except for recognizer-data set pairs (e.g., PaleoSketch recognizer and PaleoSketch data set) the results show that it outperforms the other recognizers. This demonstrates the potential of this approach to produce flexible and accurate recognizers.

关键词： Pen-Based Interfaces recognition algorithms Sketch recognition Sketch Tools

来源：评论

学校读者我要写书评

暂无评论

From modular decomposition trees to level-1 networks: Pseudo-cographs, polar-cats and prime polar-cats

引用

DISCRETE APPLIED MATHEMATICS 2022年 321卷 179-219页

作者： Hellmuth, Marc Scholz, Guillaume E. Stockholm Univ Fac Sci Dept Math SE-10691 Stockholm Sweden Univ Leipzig Dept Comp Sci Bioinformat Grp Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinforrnat Hartelstr 16-18 D-04107 Leipzig Germany

The modular decomposition of a graph G is a natural construction to capture key features of G in terms of a labeled tree (T, t) whose vertices are labeled as "series"(1), "parallel"(0) or "prime". However, full information of G is provided by its modular decomposition tree (T, t) only, if G does not contain prime modules. In this case, (T, t) explains G, i.e., {x, y} is an element of E(G) if and only if the lowest common ancestor lca(T)(x, y) of x and y has label "1". This information, however, gets lost whenever (T, t) contains vertices with label "prime". In this contribution, we aim at replacing "prime" vertices in (T, t) by simple 0/1-labeled cycles, which leads to the concept of rooted labeled level-1 networks (N, t). We characterize graphs that can be explained by such level-1 networks (N, t), which generalizes the concept of graphs that can be explained by labeled trees, that is, cographs. We provide three novel graph classes: polar-cats are a proper subclass of pseudo-cographs which forms a proper subclass of prime polar-cats. In particular, every cograph is a pseudo-cograph and prime polar-cats are precisely those graphs that can be explained by a labeled level-1 network. The class of prime polar-cats is defined in terms of the modular decomposition of graphs and the property that all prime modules "induce" polar-cats. We provide a plethora of structural results and characterizations for graphs of these new classes. In particular, Polar-cats are precisely those graphs that can be explained by an elementary level-1 network (N, t), i.e., (N, t) contains exactly one cycle C that is rooted at the root rho(N) of N and where rho(N) has exactly two children while every vertex distinct from rho(N) has a unique child that is not located in C. Pseudo-cographs are less restrictive and those graphs that can be explained by particular level-1 networks (N, t) that contain at most one cycle. These findings, eventually, help us to characterize the class of all graphs that

关键词： Cographs Modular decomposition Prime modules recognition algorithms Prime vertex replacement Phylogenetic networks Galled tree

来源：评论

学校读者我要写书评

暂无评论

LARGE-GIRTH ROOTS OF GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2010年第4期24卷 1501-1514页

作者： Adamaszek, Anna Adamaszek, Micha L. Univ Warwick Warwick Math Inst Coventry CV4 7AL W Midlands England Univ Warwick Ctr Discrete Math & Its Applicat DIMAP Coventry CV4 7AL W Midlands England

We study the problem of recognizing graph powers and computing roots of graphs. Our focus is on classes of graphs with no short cycles. We provide a polynomial time recognition algorithm for r-th powers of graphs of girth at least 2r vertical bar 3, thus improving a recently conjectured bound. Our algorithm also finds all r-th roots of a given graph that have girth at least 2r + 3 and no degree one vertices, which is a step toward a recent conjecture of Levenshtein [Discrete Math., 308 (2008), pp. 993-998] that such roots should be unique. Similar algorithms have so far been designed only for r = 2, 3. On the negative side, we prove that recognition of graph powers becomes an NP-complete problem when the bound on girth is about twice smaller.

关键词： graph roots graph powers complexity recognition algorithms

来源：评论

学校读者我要写书评

暂无评论

Recognizing Optimal 1-Planar Graphs in Linear Time

引用

ALGORITHMICA 2018年第1期80卷 1-28页

作者： Brandenburg, Franz J. Univ Passau D-94030 Passau Germany

A graph with n vertices is 1-planar if it can be drawn in the plane such that each edge is crossed at most once, and is optimal if it has the maximum of edges. We show that optimal 1-planar graphs can be recognized in linear time. Our algorithm implements a graph reduction system with two rules, which can be used to reduce every optimal 1-planar graph to an irreducible extended wheel graph. The graph reduction system is non-deterministic, constraint, and non-confluent.

关键词： Graph drawing 1-Planar graphs recognition algorithms Graph reduction systems

来源：评论

学校读者我要写书评

暂无评论

Characterising (k, l)-leaf powers

引用

DISCRETE APPLIED MATHEMATICS 2010年第2期158卷 110-122页

作者： Brandstaedt, Andreas Wagner, Peter Univ Rostock Inst Informat D-18051 Rostock Germany

We say that, for k >= 2 and l > k, a tree T with distance function d(T) (x, y) is a (k, l)-leaf root of a finite simple graph G = (V, E) if V is the set of leaves of T, for all edges xy is an element of E, d(T) (x, y) <= k, and for all non-edges xy is not an element of E, d(T) (x, y) >= l. graph is a (k, l)-leaf power if it has a (k, l)-leaf root. This new notion modifies the concept of k-leaf powers (which are, in our terminology, the (k, k + 1)-leaf powers) introduced and studied by Nishimura, Ragde and Thilikos;k-leaf powers are motivated by the search for underlying phylogenetic trees. Recently, a lot of work has been done on k-leaf powers and roots as well as on their variants phylogenetic roots and Steiner roots. Many problems, however, remain open. We give the structural characterisations of (k, l)-leaf powers, for some k and e, which also imply an efficient recognition of these classes, and in this way we improve and extend a recent paper by Kennedy, Lin and Yan on strictly chordal graphs;one of our motivations for studying (k, l)-leaf powers is the fact that strictly chordal graphs are precisely the (4, 6)-leaf powers. (C) 2009 Elsevier B.V. All rights reserved.

关键词： (k, l)-leaf powers k-leaf powers Trees Block graphs Strictly chordal graphs Characterisations recognition algorithms

来源：评论

学校读者我要写书评

暂无评论

A simple paradigm for graph recognition: application to cographs and distance hereditary graphs

引用

THEORETICAL COMPUTER SCIENCE 2001年第1-2期263卷 99-111页

作者： Damiand, G Habib, M Paul, C Univ Montpellier 2 LIRMM UMR CNRS F-34392 Montpellier 5 France Univ Bordeaux 1 LABRI F-33405 Talence France

An easy way for graph recognition algorithms is to use a two-step process: first, compute a characteristic feature as if the graph belongs to that class;second, check whether the computed feature really defines the input graph. Although in some cases the two steps can be merged, separating them may yield new and much more easily understood algorithms. In this paper we apply that paradigm to the cograph and distance hereditary graph recognition problems. (C) 2001 Elsevier Science BN. All rights reserved.

关键词： classes of graphs recognition algorithms cographs distance hereditary graphs

来源：评论

学校读者我要写书评

暂无评论

On the generalized Helly property of hypergraphs, cliques, and bicliques

引用

DISCRETE APPLIED MATHEMATICS 2023年第1期330卷 56-77页

作者： Dourado, Mitre C. Grippo, Luciano N. Safe, Martin D. Univ Fed Rio de Janeiro Inst Comp Rio De Janeiro Brazil Univ Nacl Gen Sarmiento Inst Ciencias Los Polvorines Buenos Aires Argentina Consejo Nacl Invest Cient & Tecn Buenos Aires Argentina Univ Nacl Sur UNS Dept Matemat Bahia Blanca Argentina Univ Nacl Sur UNS INMABB CONICET Bahia Blanca Argentina Dept Matemat Ave Alem 1253 Piso 2 RA-8000 Bahia Blanca Argentina

A family of sets is (p, q) -intersecting if every nonempty subfamily of p or fewer sets has at least q elements in its total intersection. A family of sets has the (p, q)-Helly property if every nonempty (p, q)-intersecting subfamily has total intersection of cardinality at least q. The (2, 1)-Helly property is the usual Helly property. A hypergraph is (p, q)-Helly if its edge family has the (p, q)-Helly property and hereditary (p, q)-Helly if each of its subhypergraphs has the (p, q)-Helly property. A graph is (p, q)-clique-Helly if the family of its maximal cliques has the (p, q)-Helly property and hereditary (p, q)-clique-Helly if each of its induced subgraphs is (p, q)-clique-Helly. The classes of (p, q)-biclique-Helly and hereditary (p, q)-biclique-Helly graphs are defined analogously. In this work, we prove several characterizations of hereditary (p, q)-Helly hypergraphs, including one by minimal forbidden partial subhypergraphs. On the algorithmic side, we give an improved time bound for the recognition of (p, q)-Helly hypergraphs for each fixed q and show that the recognition of hereditary (p, q)-Helly hypergraphs can be solved in polynomial time if p and q are fixed and co-NP-complete if p is part of the input. In addition, we generalize the characterization of p-clique-Helly graphs in terms of expansions to (p, q)-clique-Helly graphs and give different characterizations of hereditary (p, q)-clique-Helly graphs, including one by forbidden induced subgraphs. We give an improvement on the time bound for the recognition of (p, q)-clique-Helly graphs and prove that the recognition problem of hereditary (p, q)-clique-Helly graphs is polynomial-time solvable for p and q fixed and NP-hard if p or q is part of the input. Finally, we provide different characterizations, give recognition algorithms, and prove hardness results for (p, q)-biclique-Helly graphs and hereditary (p, q)-biclique-Helly graphs which are analogous to those for (p, q)-clique-Helly and hereditar

关键词： Forbidden induced subgraphs Forbidden partial subhypergraphs Generalized Helly property Helly hypergraphs Maximal cliques Maximal bicliques recognition algorithms

来源：评论

学校读者我要写书评

暂无评论

Secondary learning in the assembly neural network

引用

NEUROCOMPUTING 2004年第12期62卷 405-426页

作者： Goltsev, A Ukrainian Acad Sci VM Glushkov Cybernet Ctr Dept Neural Informat Proc Syst UA-03680 Kiev Ukraine

A neural network with assembly organization is described, The network is artificially partitioned into several sub-networks according to the number of classes that the network has to recognize. The features extracted from input data are encoded into activation of certain patterns of neurons in the sub-networks. During a process of primary learning, Hebb's neural assemblies are formed in the sub-networks by means of modification of connections' weights. A procedure of secondary learning, which is named as that of differentiation, is described. The procedure is intended to improve a recognition accuracy of the network by means of additional modification of connections' weights between the neurons of the same sub-networks. A computer simulation of the network is performed. The differentiation process is studied in a set of experiments on a character recognition task using two types of objects: Ukrainian letters and Arabic numerals of modified US National Institute of Standards and Technology (MNIST) database. (C) 2004 Elsevier B.V. All rights reserved.

关键词： neurons neural assemblies learning features connection weights procedure of differentiation recognition algorithms

来源：评论

学校读者我要写书评

暂无评论

Using data mining for digital ink recognition: Dividing text and shapes in sketched diagrams

引用

COMPUTERS & GRAPHICS-UK 2011年第5期35卷 976-991页

作者： Blagojevic, Rachel Plimmer, Beryl Grundy, John Wang, Yong Univ Auckland Auckland 1 New Zealand Swinburne Univ Technol Hawthorn Vic 3122 Australia

The low accuracy rates of text-shape dividers for digital ink diagrams are hindering their use in real world applications. While recognition of handwriting is well advanced and there have been many recognition approaches proposed for hand drawn sketches, there has been less attention on the division of text and drawing ink. Feature based recognition is a common approach for text-shape division. However, the choice of features and algorithms are critical to the success of the recognition. We propose the use of data mining techniques to build more accurate text-shape dividers. A comparative study is used to systematically identify the algorithms best suited for the specific problem. We have generated dividers using data mining with diagrams from three domains and a comprehensive ink feature library. The extensive evaluation on diagrams from six different domains has shown that our resulting dividers, using LADTree and LogitBoost, are significantly more accurate than three existing dividers. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Sketch tools recognition algorithms Sketch recognition Pen-based interfaces

来源：评论

学校读者我要写书评

暂无评论

On the complexity of recognizing directed path families

引用

DISCRETE APPLIED MATHEMATICS 2009年第11期157卷 2525-2535页

作者： Apollonio, N. Frandosa, P. G. Univ Roma La Sapienza Dipartimento Stat Probabil & Stat Applicate I-00185 Rome Italy

A Directed Path Family is a family of subsets of some finite ground set whose members call be realized as arc sets of simple directed paths in some directed graph. In this paper we show that recognizing whether a given family is a Directed Path family is an NP-Complete problem, even when all members in the family have at most two elements. If instead of a family of subsets, we are given a collection of words from some finite alphabet, then deciding whether there exists a directed graph G Such that each word ill the language is the set of arcs of some path in G, is a polynomial-time solvable problem. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Directed line graph Hypergraph 2-colorability recognition algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：