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

DISCRETE APPLIED MATHEMATICS 2011年第7期159卷 595-604页

作者： Jamison, Robert E. Clemson Univ Clemson SC 29634 USA Univ Haifa IL-31999 Haifa Israel

An edge coloring of a graph is orientable if and only if it is possible to orient the edges of the graph so that the color of each edge is determined by the head of its corresponding oriented arc. The goals of this paper include finding a forbidden substructure characterization of orientable colorings and giving a linear time recognition algorithm for orientable colorings. An edge coloring is lexical if and only if it is possible to number the vertices of the graph so that the color of each edge is determined by its lower endpoint. Lexical colorings are, of course, the orientable colorings in which the underlying orientation is acyclic. Lexical colorings play an important role in Canonical Ramsey theory, and it is this standpoint that motivates the current study. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Edge coloring Directed graph Orientation Closure Forbidden substructure recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

A mathematical programming approach for recognizing binet matrices

引用

OPTIMIZATION LETTERS 2024年第6期18卷 1511-1532页

作者： Papalamprou, Konstantinos Pitsoulis, Leonidas Kotnyek, Balasz Aristotle Univ Thessaloniki Elect & Comp Engn Dept Thessaloniki Greece London Sch Econ Dept Operat Res London England

The development of an efficient and practical method to recognize matrices originating from generalized graphs, in the same way that network matrices are defined over directed graphs, remains an open question. In this paper we present such a recognition procedure for binet matrices which are known to characterize an important class of integral polyhedra. A mathematical programming formulation for the recognition problem is provided, where the special structure of these matrices is expressed via a set of constraints. Finally, given that binet matrices represent certain classes of matroids, we present a set of areas ranging from combinatorial optimization to matroid theory that can benefit from our approach.

关键词： recognition algorithm Integer programming Binet matrices Signed-graphic matroids

来源：评论

学校读者我要写书评

暂无评论

A characterization of partial directed line graphs

引用

DISCRETE MATHEMATICS 2007年第21期307卷 2598-2614页

作者： Apollonio, Nicola Franciosa, Paolo G. Univ Roma La Sapienza Dipartimento Stat Probabilita & Stat Applicate I-00185 Rome Italy

Can a directed graph be completed to a directed line graph? If possible, how many arcs must be added? In this paper we address the above questions characterizing partial directed line (PDL) graphs, i.e., partial subgraph of directed line graphs. We show that for such class of graphs a forbidden configuration criterion and a Krausz's like theorem are equivalent characterizations. Furthermore, the latter leads to a recognition algorithm that requires O(m) worst case time, where m is the number of arcs in the graph. Given a partial line digraph, our characterization allows us to find a minimum completion to a directed line graph within the same time bound. The class of PDL graphs properly contains the class of directed line graphs, characterized in [J. Blazewicz, A. Hertz, D. Kobler, D. de Werra, On some properties of DNA graphs, Discrete Appl. Math. 98(1-2) (1999) 1-19], hence our results generalize those already known for directed line graphs. In the undirected case, we show that finding a minimum line graph edge completion is NP-hard. while the problem of deciding whether or not an undirected graph is a partial graph of a simple line graph is trivial. (C) 2007 Elsevier B.V. All rights reserved.

关键词： line digraphs line graph completion recognition algorithm NP-completeness

来源：评论

学校读者我要写书评

暂无评论

On graphs without a C₄ or a diamond

引用

DISCRETE APPLIED MATHEMATICS 2011年第7期159卷 581-587页

作者： Eschen, Elaine M. Hoang, Chinh T. Spinrad, Jeremy P. Sritharan, R. W Virginia Univ Lane Dept Comp Sci & Elect Engn Morgantown WV 26506 USA Wilfrid Laurier Univ Dept Phys & Comp Waterloo ON N2L 3C5 Canada Vanderbilt Univ Dept Elect Engn & Comp Sci Nashville TN 37235 USA Univ Dayton Dept Comp Sci Dayton OH 45469 USA

We consider the class of (C-4, diamond)-free graphs;graphs in this class do not contain a C-4 or a diamond as an induced subgraph. We provide an efficient recognition algorithm for this class. We count the number of maximal cliques in a (C-4, diamond)-free graph and the number of n-vertex, labeled (C-4, diamond)-free graphs. We also give an efficient algorithm for finding a largest clique in the more general class of (house, diamond)-free graphs. (C) 2010 Elsevier B.V. All rights reserved.

关键词： C-4-free graphs Diamond-free graphs recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

On the recognition of permuted Supnick and incomplete Monge matrices

引用

ACTA INFORMATICA 1996年第6期33卷 559-569页

作者： Deineko, V Rudolf, R Woeginger, GJ GRAZ TECH UNIV INST MATHA-8010 GRAZAUSTRIA

Incomplete Monge matrices are a generalization of standard Monge matrices: the values of some entries are not specified and the Monge property only must hold for all specified entries. We derive several combinatorial properties of incomplete Monge matrices and prove that the problem of recognizing permuted incomplete Monge matrices is NP-complete. For the special case of permuted Supnick matrices, we derive a fast recognition algorithm and thereby identify a special case of the n-vertex travelling salesman problem which can be solved in O (n(2) log n) time.

关键词： Travel Salesman Problem recognition algorithm Combinatorial Property Fast recognition Monge Property

来源：评论

学校读者我要写书评

暂无评论

A Simpler Linear-Time recognition of Circular-Arc Graphs

引用

algorithmICA 2011年第3期61卷 694-737页

作者： Kaplan, Haim Nussbaum, Yahav Tel Aviv Univ Blavatnik Sch Comp Sci IL-69978 Tel Aviv Israel

We give a linear-time recognition algorithm for circular-arc graphs based on the algorithm of Eschen and Spinrad (Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 128-137, 1993) and Eschen (PhD thesis, 1997). Our algorithm both improves the time bound of Eschen and Spinrad, and fixes some flaws in it. Our algorithm is simpler than the earlier linear-time recognition algorithm of McConnell (algorithmica 37(2):93-147, 2003), which is the only linear time recognition algorithm previously known.

关键词： Circular-arc graph Circular-arc model recognition algorithm Intersection graph Consecutive-ones property

来源：评论

学校读者我要写书评

暂无评论

Household appliance recognition through a Bayes classification model

引用

SUSTAINABLE CITIES AND SOCIETY 2019年 46卷 101393-000页

作者： Yan, Da Jin, Yuan Sun, Hongsan Dong, Bing Ye, Zi Li, Zhaoxuan Yuan, Yanping Tsinghua Univ Sch Architecture Beijing Peoples R China Univ Texas San Antonio Dept Mech Engn San Antonio TX USA Southwest Jiaotong Univ Sch Mech Engn Chengdu Sichuan Peoples R China

With the acceleration of global warming and energy shortages, the smart grid has become the goal of power grid development, which makes intelligent household appliance control systems essential. To promote the integration of traditional household appliances into a new electrical system, this study focused on an appliance recognition algorithm applicable to traditional and typical household appliances. Using sequential appliance power consumption data from intelligent power sockets, this study generalized and extracted the characteristics of occupant behavior and power consumption of typical household appliances. A new recognition algorithm for household appliances, based on a Bayes classification model, is presented in this paper. Seven types of household appliances (refrigerator, electric cooker, air conditioner, television, laptop computer, washing machine, and water dispenser) were analyzed in 15 Beijing households. The proposed algorithm was proven to be applicable for appliance recognition.

关键词： Household appliances recognition algorithm Bayes classification Occupant behavior Smart grid

来源：评论

学校读者我要写书评

暂无评论

POLYHEDRAL OBJECT recognition WITH SPARSE DATA IN SIMD PROCESSING MODE

引用

IMAGE AND VISION COMPUTING 1989年第1期7卷 71-78页

作者： HOLDER, D BUXTON, H QUEEN MARY COLL DEPT COMP SCILONDON E1 4NSENGLAND

The method of Grimson, Lozano Pérez and others for the recognition of polyhedral objects with sparse data, has been developed and implemented on a distributed array processor, the AMT DAP 500, which operates in single instruction-multiple data (SIMD) mode. Measurements involving the location vectors and the surface normals at m data points, considered in pairs, are compared with the corresponding maximum and minimum values associated with n × n pairs of object model faces in a process that exploits n × n parallelism. The overall processing time is essentiallv proportional to m × (m−1) 2 to explore the interpretation tree to its full depth. This paper discusses the nature of the comparisons between object models and data, together with the need to make these comparisons in a particular sequence, and results of test runs with a variety of object models and different geometric constraints are presented herein. Comparison is made with the corresponding sequential process, and with the more costly method of Flynn and Harris, in which n m processing elements are required to acheive, at best a processing time of the same order of magnitude.

关键词： object recognition recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithms for perfectly contractile graphs

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2005年第3期19卷 553-574页

作者： Maffray, F Trotignon, N Imag Lab Grenoble CNRS Lab Leibniz F-38031 Grenoble France

We consider the class A of graphs that contain no odd hole, no antihole of length at least 5, and no prism ( a graph consisting of two disjoint triangles with three disjoint paths between them) and the class A' of graphs that contain no odd hole, no antihole of length at least 5, and no odd prism ( prism whose three paths are odd). These two classes were introduced by Everett and Reed and are relevant to the study of perfect graphs. We give polynomial-time recognition algorithms for these two classes. In contrast we prove that determining if a general graph contains a prism ( or an even prism, or an odd prism) is NP-complete.

关键词： perfect graph even pair perfectly contractile recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

Fault classifications of MV transmission lines connected to wind farms using non-intrusive fault monitoring techniques on HV utility side

引用

IET GENERATION TRANSMISSION & DISTRIBUTION 2020年第26期14卷 6518-6525页

作者： Chang, Hsueh-Hsien Jinwen Univ Sci & Technol Dept Comp & Commun Engn New Taipei Taiwan

The fault classification of medium-voltage transmission lines consisting of wind farms connected to the high-voltage (HV) transmission networks is carried out using the power-spectrum-based hyperbolic S-transform (HST) powerful technique for analysing non-linear and non-stationary fault signals through the non-intrusive monitoring systems. The HST technique extracts the useful features in the time-frequency domain from measuring fault current waveforms of the HV utility side to discriminate the fault types. Parseval's theorem is applied to each HST coefficient to quantify the energy distribution of various fault types for reducing the size of inputs for recognition algorithms. Next, multiclass support vector machines achieve identification. The results have proved that the proposed classification technique is independent of fault resistance, source impedance, and fault inception angles. Extensive simulations are conducted using the electromagnetic transients program to show that the recognition accuracy of the fault classification for all types is up to 96.84%.

关键词： time-frequency analysis power transmission lines wind power plants fault currents support vector machines feature extraction power transmission faults fault diagnosis EMTP power transmission protection fault classification MV transmission lines wind farms nonintrusive fault monitoring techniques HV utility side medium-voltage transmission lines high-voltage transmission networks nonstationary fault signals HST technique fault current waveforms fault resistance fault inception angles power-spectrum-based hyperbolic S-transform technique time-frequency domain feature extraction energy distribution recognition algorithm multiclass support vector machine electromagnetic transients program

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：