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

Clique-perfectness and balancedness of some graph classes

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2014年第10期91卷 2118-2141页

作者： Bonomo, Flavia Duran, Guillermo Safe, Martin D. Wagler, Annegret K. Univ Buenos Aires CONICET Buenos Aires DF Argentina Univ Buenos Aires FCEN Dept Comp Buenos Aires DF Argentina Univ Buenos Aires CONICET Inst Calculo Buenos Aires DF Argentina Univ Buenos Aires FCEN Dept Matemat Buenos Aires DF Argentina Univ Chile FCFM Dept Ingn Ind Santiago Chile Univ Nacl Gen Sarmiento Inst Ciencias Los Polvorines Argentina Univ Blaise Pascal CNRS Aubiere France Univ Blaise Pascal LIMOS UFR Sci & Tech Aubiere France

A graph is clique-perfect if the maximum size of a clique-independent set (a set of pairwise disjoint maximal cliques) and the minimum size of a clique-transversal set (a set of vertices meeting every maximal clique) coincide for each induced subgraph. A graph is balanced if its clique-matrix contains no square submatrix of odd size with exactly two ones per row and column. In this work, we give linear-time recognition algorithms and minimal forbidden induced subgraph characterizations of clique-perfectness and balancedness of P-4-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for any P-4-tidy graph. We also give a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for balancedness of paw-free graphs. Finally, we show that clique-perfectness of diamond-free graphs can be decided in polynomial time by showing that a diamond-free graph is clique-perfect if and only if it is balanced.

关键词： 05C75 05C17 05C85 clique-perfect graphs balanced graphs diamond-free graphs recognition algorithms paw-free graphs P-4-tidy graphs

来源：评论

学校读者我要写书评

暂无评论

On some properties of DNA graphs

引用

DISCRETE APPLIED MATHEMATICS 1999年第1-2期98卷 1-19页

作者： Blazewicz, J Hertz, A Kobler, D de Werra, D Ecole Polytech Fed Lausanne Dept Math MA Ecublens CH-1015 Lausanne Switzerland Politechn Poznanka Inst Informat Poznan Poland

Molecular biology which aims to study DNA and protein structure and functions, has stimulated research in different scientific disciplines, discrete mathematics being one of them. One of the problems considered is that of recognition of DNA primary structure. It is known that some methods for solving this problem may be reduced (in their computational part) to graph-theoretic problems involving labeled graphs. Each vertex in such graphs has a label of length k written with an alphabet of size alpha, where k and alpha are two parameters. This paper is concerned with studying propel ties of these graphs (referred to as DNA graphs). More precisely, we give recognition algorithms and compare graphs labeled with different values of k and alpha. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： DNA graphs protein structure and functions recognition algorithms

来源：评论

学校读者我要写书评

暂无评论

recognition of Unipolar and Generalised Split Graphs

引用

algorithms 2015年第1期8卷 46-59页

作者： McDiarmid, Colin Yolov, Nikola Univ Oxford Dept Stat Oxford OX1 3TG England Univ Oxford Dept Comp Sci Wolfson BldgPk Rd Oxford OX1 3QD England

A graph is unipolar if it can be partitioned into a clique and a disjoint union of cliques, and a graph is a generalised split graph if it or its complement is unipolar. A unipolar partition of a graph can be used to find efficiently the clique number, the stability number, the chromatic number, and to solve other problems that are hard for general graphs. We present an O(n(2))-time algorithm for recognition of n-vertex generalised split graphs, improving on previous O(n(3))-time algorithms.

关键词： generalised split graphs perfect graphs recognition algorithms representations unipolar graphs

来源：评论

学校读者我要写书评

暂无评论

Implementation of a Method for Constructing a recognition Algorithm in Algebra over an Estimate Calculation Set

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2008年第9期48卷 1680-1686页

作者： Romanov, M. Yu. Moscow Inst Phys & Technol Dolgoprudnyi 141700 Moscow Oblast Russia

A method is implemented for constructing an algorithm in algebra over an estimate calculation set in an algebraic extension of the least degree.

关键词： recognition algorithms algebra over an estimate calculation set

来源：评论

学校读者我要写书评

暂无评论

DISTINCTIVE FEATURES IN AUTOMATIC recognition OF HANDPRINTED CHARACTERS

引用

SIGNAL PROCESSING 1982年第2-3期4卷 193-207页

作者： SUEN, CY Department of Computer Science Concordia University Montreal Canada H3G 1M8

Characters are recognized from the features extracted. Usually the input chacter is smoothed and cleaned by the preprocessor before it reaches the featuree extractor. Good preprocessors and feature extractors are the prerequisites to a successful character recognition system. Following a description of preprocessing techniques, the various features found in the vast accumulation of literature on handprint recognition are divided into two main categories: (1) global analysis, and (2) structural analysis. Further subdivision of these categories gives rise to six families of feature type, viz. (a) distribution of points, (b) transformation, (c) physical measurements, (d) line segments and edges, (e) outline of character, and (f) centre-line of character. Each family is described with illustrative examples. The performance and recognition rates of systems employing these features are discussed. Zusammenfassung Zeichen werden aufgrund von Merkmalen erkannt. Üblicherweise wird einzu erkennedes Zeichen in der Vorverarbeitungsstufe geglättet und ‘gesäubert’, bevor es den Merkmalsextraktor erreicht. Gute Vorverarbeitungsstufen und Merkmalsextraktoren sind hierbei die Voraussetzung für erfolgreiches Arbeiten eines Zeichenerkennungssystems. In diesem Beitrag werden zunächst einige Prinzipien der Vorverarbeitung beschrieben; hierauf werden die verschiedenen Verarbeitungsmethoden, die sich in dem umfangreichen Schrifttum über die automatische Erkennung handschriftlicher Zeichen finden, in zwei Hauptkategorien eingeteilt: (1) globale Analyse sowie (2) strukturelle Analyse. Eine weitere Unterteilung dieser Kategorien ergibt je nach Verarbeitungsmethode sechs Merkmalsfamilien: (a) Verteilung der Zeichenpunkte, (b) Transformation, (c) physikalische Messungen, (d) Liniensegmente und Ränder, (e) Umriβ sowie (f) Skelett des Zeichens. Jede dieser Merkmalsfamilien wird beschrieben und anhand von Beispielen erklärt. Abschlieβend wird die Wirkungsweise und die Erkennungsrate von Erkennungs

关键词： Feature extraction handprint recognition recognition algorithms

来源：评论

学校读者我要写书评

暂无评论

On proportions of pre-involutions in finite classical groups

引用

JOURNAL OF ALGEBRA 2010年第5期324卷 1016-1043页

作者： Niemeyer, Alice C. Popiel, Tomasz Praeger, Cheryl E. Univ Western Australia Sch Math & Stat M019 Crawley WA 6009 Australia

Key to a computational study of the finite classical groups in odd characteristic are efficient methods for constructing involutions and their centralisers. Constructing an involution in a given conjugacy class is usually achieved by finding an element of even order that powers up to an involution in the class. Lower bounds on the proportions of such elements are therefore required to control the failure probability of these algorithms. Previous results of Christopher Parker and Robert Wilson give an O(n(-3)) lower bound that holds for all involution classes in n-dimensional simple classical groups in odd characteristic. We improve this lower bound to O(n(-2) log n), and in certain cases to O(n(-1)), and also treat a larger family of (not necessarily simple) classical groups. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Finite classical groups Involutions Proportions recognition algorithms

来源：评论

学校读者我要写书评

暂无评论

Neighborhood covering and independence on P4\documentclass[12pt]-tidy graphs and tree-cographs

引用

ANNALS OF OPERATIONS RESEARCH 2020年第1-2期286卷 55-86页

作者： Duran, Guillermo Safe, Martin Warnes, Xavier Univ Buenos Aires Fac Ciencias Exactas & Nat Inst Calculo Buenos Aires DF Argentina Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Matemat Buenos Aires DF Argentina Univ Chile Fac Ciencias Fis & Matemat Dept Ingn Ind Santiago Chile Consejo Nacl Invest Cient & Tecn Buenos Aires DF Argentina Univ Nacl Sur Dept Matemat Bahia Blanca Buenos Aires Argentina Stanford Univ Grad Sch Business Stanford CA 94305 USA

Given a simple graph G, a set C subset of V(G)\documentclass[12pt] is a neighborhood cover set if every edge and vertex of G belongs to some G[v] with v is an element of C\documentclass[12pt] denotes the subgraph of G induced by the closed neighborhood of the vertex v. Two elements of E(G)?V(G)\documentclass[12pt] are neighborhood-independent if there is no vertex v is an element of V(G)\documentclass[12pt]such that both elements are in G[v]. A set S subset of V(G)?E(G)\documentclass[12pt] is neighborhood-independent if every pair of elements of S is neighborhood-independent. Let rho n(G)\documentclass[12pt] be the size of a minimum neighborhood cover set and alpha n(G)\documentclass[12pt] of a maximum neighborhood-independent set. Lehel and Tuza defined neighborhood-perfect graphs G as those where the equality rho n(G ')=alpha n(G ')\documentclass[12pt] holds for every induced subgraph G-documentclass[12pt] of G. In this work we prove forbidden induced subgraph characterizations of the class of neighborhood-perfect graphs, restricted to two superclasses of cographs: P4\documentclass[12pt]-tidy graphs and tree-cographs. We give as well linear-time algorithms for solving the recognition problem of neighborhood-perfect graphs and the problem of finding a minimum neighborhood cover set and a maximum neighborhood-independent set in these same classes. Finally we prove that although for complements of trees finding these optimal sets can be achieved in linear-time, for complements of bipartite graphs it is NP\documentclass[12pt]-hard.

关键词： Forbidden induced subgraphs Neighborhood-perfect graphs P-4-tidy graphs Tree-cographs recognition algorithms Co-bipartite graphs

来源：评论

学校读者我要写书评

暂无评论

COMPUTER recognition OF UNCONSTRAINED HANDWRITTEN NUMERALS

引用

PROCEEDINGS OF THE IEEE 1992年第7期80卷 1162-1180页

作者： SUEN, CY NADAL, C LEGAULT, R MAI, TA LAM, L CONCORDIA UNIV DEPT COMP SERVMONTREAL H3G 1M8QUEBECCANADA

In this paper we present four algorithms developed independently by members of our research team specialized in recognition of unconstrained handwritten numerals. All these methods have high recognition rates and are considered experts by our research group. We also present the different ways experimented on for incorporation of these recognition methods into a more powerful system. By combining them we realize that they complement each other in many ways. The resulting multiple-expert system proves that the consensus of these methods tends to compensate for individual weaknesses, while preserving individual strengths. This paper shows that it is possible to reduce the substitution rate to a desired level while maintaining a fairly high recognition rate in the classification of totally unconstrained handwritten ZIP code numerals. Furthermore, if reliability is of the utmost importance, we can avoid substitutions completely (reliability = 100%) and still retain a recognition rate above 90%. In the last part of this paper, we try to compare results given by some of the most effective numeral recognition systems found in the literature.

关键词： CHARACTER recognition OCR HANDWRITTEN NUMERALS recognition algorithms MULTIPLE EXPERTS COMBINATION OF EXPERT DECISIONS

来源：评论

学校读者我要写书评

暂无评论

Strong involutions in finite special linear groups of odd characteristic

引用

JOURNAL OF ALGEBRA 2018年 498卷 413-447页

作者： Dixon, John D. Praeger, Cheryl E. Seress, Akos Carleton Univ Sch Math & Stat Ottawa ON K1S 5B6 Canada Univ Western Australia Sch Phys Math & Comp Crawley WA 6009 Australia

Let t be an involution in GL(n, q) whose fixed point space E+ has dimension k between n/3 and 2n/3. For each g is an element of GL(n, q) such that tt(9) has even order, contains a unique involution z(g) which commute... 详细信息

Let t be an involution in GL(n, q) whose fixed point space E+ has dimension k between n/3 and 2n/3. For each g is an element of GL(n, q) such that tt(9) has even order, < tt(g)> contains a unique involution z(g) which commutes with t. We prove that, with probability at least c/log n (for some c > 0), the restriction z(g)(vertical bar E+) is an involution on E+ with fixed point space of dimension between k/3 and 2k/3. This result has implications in the analysis of the complexity of recognition algorithms for finite classical groups in odd characteristic. We discuss how similar results for involutions in other finite classical groups would solve a major open problem in our understanding of the complexity of constructing involution centralisers in those groups. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Finite classical groups Involution centralisers recognition algorithms

来源：评论

学校读者我要写书评

暂无评论

Involution centralisers in finite unitary groups of odd characteristic

引用

JOURNAL OF ALGEBRA 2020年 545卷 245-299页

作者： Glasby, S. P. Praeger, Cheryl E. Roney-Dougal, Colva M. UWA Dept Math & Stat Perth WA 6009 Australia Univ St Andrews Math Inst St Andrews KY16 9SS Fife Scotland

We analyse the complexity of constructing involution centralisers in unitary groups over fields of odd order. In particular, we prove logarithmic bounds on the number of random elements required to generate a subgroup of the centraliser of a strong involution that contains the last term of its derived series. We use this to strengthen previous bounds on the complexity of recognition algorithms for unitary groups in odd characteristic. Our approach generalises and extends two previous papers by the second author and collaborators on strong involutions and regular semisimple elements of linear groups. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Involution centralisers recognition algorithms Classical groups Unitary groups Regular semisimple elements Group generation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：