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

Signal recognition without State Space Expansion Based on Observations Containing a Singular Interference: The Case of Nonlinear Parameters of Basis Functions

引用

AUTOMATION AND REMOTE CONTROL 2024年第2期85卷 147-161页

作者： Bulychev, Yu. G. JSC Concern Radioelect Technol Moscow Russia

This paper proposes a novel method for recognizing a set of signals with linearly and nonlinearly included parameters from a given ensemble of signals under essential a priori uncertainty. Due to this uncertainty, well-known statistical methods become inapplicable. Signals may be present in an additive mixture containing an observation noise and a singular interference;the distribution law of the noise is unknown, and only its correlation matrix is specified. The novel method is invariant to this interference, does not require traditional state-space expansion, and ensures the decomposition and parallelization of the computational procedure. The signals and interference are represented using conventional linear spectral decompositions with unknown coefficients and given basis functions. Random and methodological errors, as well as the resulting computational effect, are analyzed. An illustrative example is provided.

关键词： essential a priori uncertainty singular interference basis functions with nonlinear parameters spectral coefficients state space expansion optimal estimation unbiased estimation invariance to interference recognition algorithm decomposition parallel computing

来源：评论

学校读者我要写书评

暂无评论

recognition of overlap graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2014年第1期28卷 25-37页

作者： Gevezes, Theodoros P. Pitsoulis, Leonidas S. Aristotle Univ Thessaloniki Dept Math Phys & Computat Sci Thessaloniki 54124 Greece

Overlap graphs occur in computational biology and computer science, and have applications in genome sequencing, string compression, and machine scheduling. Given two strings and , their overlap string is defined as the longest string such that and , for some non empty strings , and its length is called the overlap between these two strings. A weighted directed graph is an overlap graph if there exists a set of strings with one-to-one correspondence to the vertices of the graph, such that each arc weight in the graph equals the overlap between the corresponding strings. In this paper, we characterize the class of overlap graphs, and we present a polynomial time recognition algorithm as a direct consequence. Given a weighted directed graph , the algorithm constructs a set of strings that has as its overlap graph, or decides that this is not possible.

关键词： Strings Shortest superstring problem Overlap graphs recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

Signed-graphic matroids with all-graphic cocircuits

引用

DISCRETE MATHEMATICS 2017年第12期340卷 2889-2899页

作者： Papalamprou, Konstantinos Pitsoulis, Leonidas S. Aristotle Univ Thessaloniki Dept Elect & Comp Engn Thessaloniki 54124 Greece

A matroid M has all-graphic cocircuits if M\Y is a graphic matroid for every cocircuit Y is an element of C*(M). In Papalamprou and Pitsoulis (2013) it has been shown that signed-graphic matroids that are representable in GF(2) can be decomposed into graphic matroids and matroids with all-graphic cocircuits. In this paper we study this class of signed-graphic matroids with all-graphic cocircuits and provide the set of regular excluded minors as well as a complete characterization when the matroid is cographic, which in turn results in a simple recognition algorithm. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Signed graphs recognition algorithm All-graphic cocircuits

来源：评论

学校读者我要写书评

暂无评论

GRAPH SANDWICH PROBLEMS

引用

JOURNAL OF algorithmS-COGNITION INFORMATICS AND LOGIC 1995年第3期19卷 449-473页

作者： GOLUMBIC, MC KAPLAN, H SHAMIR, R PRINCETON UNIV DEPT COMP SCI PRINCETON NJ 08544 USA TEL AVIV UNIV SACKLER FAC EXACT SCI DEPT COMP SCI IL-69978 TEL AVIV ISRAEL

The graph sandwich problem for property Pi: is defined as follows: Given two graphs G(1) = (V, E(1)) and G(2) = (V, E(2)) such that E(1) subset of or equal to E(2), is there a graph G = (V, E) such that E(1) subset of or equal to E subset of or equal to E(2) which satisfies property Pi? Such problems generalize recognition problems and arise in various applications. Concentrating mainly on properties characterizing subfamilies of perfect graphs, we give polynomial algorithms for several properties and prove the NP-completeness of others. We describe polynomial time algorithms for threshold graphs, split graphs, and cographs. For the sandwich problem for threshold graphs, the only case in which a previous algorithm existed, we obtain a faster algorithm. NP-completeness proofs are given for comparability graphs, permutation graphs, and several other families. For Eulerian graphs;one Version of the problem is polynomial and another is NP-complete. (C) 1995 Academic Press, Inc.

关键词： recognition algorithm Intersection graphs Trees Complexity Paths Time Subset Complexity Equal Trees Paths Polynomial Byways

来源：评论

学校读者我要写书评

暂无评论

The (theta, wheel)-free graphs Part I: Only-prism and only-pyramid graphs

引用

JOURNAL OF COMBINATORIAL THEORY SERIES B 2020年 143卷 123-147页

作者： Diot, Emilie Radovanovic, Marko Trotignon, Nicolas Vuskovic, Kristina ENS Lyon LIP Lyon France Univ Belgrade Fac Math Belgrade Serbia ENS Lyon CNRS LIP Lyon France Univ Leeds Sch Comp Leeds W Yorkshire England Union Univ Fac Comp Sci RAF Belgrade Serbia

Truemper configurations are four types of graphs (namely thetas, wheels, prisms and pyramids) that play an important role in the proof of several decomposition theorems for hereditary graph classes. In this paper, we prove two structure theorems: one for graphs with no thetas, wheels and prisms as induced subgraphs, and one for graphs with no thetas, wheels and pyramids as induced subgraphs. A consequence is a polynomial time recognition algorithms for these two classes. In Part II of this series we generalize these results to graphs with no thetas and wheels as induced subgraphs, and in Parts III and IV, using the obtained structure, we solve several optimization problems for these graphs. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Structure theorem Decomposition Truemper configuration recognition algorithm Induced subgraph Clique cutset 2-Join

来源：评论

学校读者我要写书评

暂无评论

RECOGNIZING PATTERNS - ARE THERE PROCESSES THAT PRECEDE FEATURE ANALYSIS

引用

PATTERN recognition 1975年第1-2期7卷 95-106页

作者： TUNSTALL, KW YORK UNIV FAC ADM STUDIES4700 KEELE STDOWNSVIEW M3J 2R6ONTARIOCANADA

The paper presents evidence to suggest that the feature analytic process is insufficient to account for the phenomenon of pattern recognition. It is suggested that two processes are necessary prior to feature analysis. The first is termed perceptual input, and serves to define the context of each perceptual unit. (The perceptual unit is defined as the context-sensitive point, not the context-free feature.) the second process is termed figure-ground synthesis, and is seen to yield figural unity and context. General evidence supportive of the model is adduced. A rigorous formulation of this pre-analytic model is presented. In its detail, the model is, of course, highly speculative. A test of the model involving hand simulation with a complex example is presented. The paper concludes by noting certain shortcomings of the model and a likely next step in development.

关键词： Feature analysis Pre-analytic process Context-sensitive Psychological evidence recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

Local structure when all maximal independent sets have equal weight

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 1998年第4期11卷 644-654页

作者： Caro, Y Ellingham, MN Ramey, JE Univ Haifa Oranim Sch Educ Dept Math IL-36006 Tivon Israel Vanderbilt Univ Dept Math Nashville TN 37240 USA Cumberland Coll Dept Math Williamsburg KY 40769 USA

In many combinatorial situations there is a notion of independence of a set of points. Maximal independent sets can be easily constructed by a greedy algorithm, and it is of interest to determine, for example, if they all have the same size or the same parity. Both of these questions may be formulated by weighting the points with elements of an abelian group, and asking whether all maximal independent sets have equal weight. If a set is independent precisely when its elements are pairwise independent, a graph can be used as a model. The question then becomes whether a graph, with its vertices weighted by elements of an abelian group, is well-covered, i.e., has all maximal independent sets of vertices with equal weight. This problem is known to be co-NP-complete in general. We show that whether a graph is well-covered or not depends on its local structure. Based on this, we develop an algorithm to recognize well-covered graphs. For graphs with n vertices and maximum degree Delta, it runs in linear time if Delta is bounded by a constant, and in polynomial time if Delta = O((3)root log n). We mention various applications to areas including hypergraph matchings and radius k independent sets. We extend our results to the problem of determining whether a graph has a weighting which makes it well-covered.

关键词： well-covered graph maximal independent set local structure polynomial time algorithm recognition algorithm hypergraph matching independence system

来源：评论

学校读者我要写书评

暂无评论

Unique square property and fundamental factorizations of graph bundles

引用

DISCRETE MATHEMATICS 2002年第1-3期244卷 551-561页

作者： Zmazek, B Zerovnik, J Univ Maribor Fac Mech Engn FS SLO-2000 Maribor Slovenia Univ Maribor Dept Math PEF SLO-2000 Maribor Slovenia Inst Math Phys & Mech Dept Theoret Comp Sci Ljubljana 1111 Slovenia

Graph bundles generalize the notion of covering graphs and graph products. In Imrich et al. (Discrete Math. 167/168 (1998) 393) authors constructed an algorithm that finds a presentation as a nontrivial cartesian graph bundle for all graphs that are cartesian graph bundles over triangle-free simple base using the relation delta(*) having the square property. An equivalence relation R on the edge set of a graph has the (unique) square property if and only if any pair of adjacent edges which belong to distinct R-equivalence classes span exactly one induced 4-cycle (with opposite edges in the same R-equivalence class). In this paper we define the unique square property and show that any weakly 2-convex equivalence relation possessing the unique square property determines the fundamental factorization of a graph as a nontrivial cartesian graph bundle over an arbitrary base graph, whenever it separates degenerate and nondegenerate edges of the factorization. (C) 2002 Elsevier Science B.V. All rights: reserved.

关键词： graph bundles Cartesian graph bundles recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

A New Characterization of V-Posets

引用

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS 2020年第2期37卷 371-387页

作者： Cooper, Joshua Gartland, Peter Whitlatch, Hays Univ South Carolina Dept Math 1523 Greene St Columbia SC 29208 USA Univ Calif Santa Barbara Dept Comp Sci Harold Frank Hall Lagoon Rd Santa Barbara CA 93106 USA Gonzaga Univ Dept Math 502 E Boone Ave Spokane WA 99258 USA

Hasebe and Tsujie characterized the set of induced N-free and bowtie-free posets as a certain class of recursively defined subposets which they term "V-posets". Here we offer a new characterization of V-posets by introducing a property we refer to as autonomy. A poset P is said to be autonomous if there exists a directed acyclic graph D (with adjacency matrix U) whose transitive closure is P, with the property that any total ordering of the vertices of D so that Gaussian elimination of UT U proceeds without row swaps is a linear extension of P. Autonomous posets arise from the theory of pressing sequences in graphs, a problem with origins in computational evolutionary biology. The pressing sequences of a graph can be partitioned into families corresponding to posets;because of the interest in enumerating pressing sequences, we investigate when this partition has only one block, that is, when the pressing sequences are all linear extensions of a single autonomous poset. We also provide an efficient algorithm for recognition of autonomy using structural information and the forbidden subposet characterization, and we discuss a few open questions that arise in connection with these posets.

关键词： Poset Pressing sequence recognition algorithm N-free Bowtie-free Graph theory

来源：评论

学校读者我要写书评

暂无评论

Decomposition of even-hole-free graphs with star cutsets and 2-joins

引用

JOURNAL OF COMBINATORIAL THEORY SERIES B 2013年第1期103卷 144-183页

作者： da Silva, Murilo V. G. Vuskovic, Kristina Univ Tecnol Fed Parana DAINF Curitiba Parana Brazil Univ Leeds Sch Comp Leeds LS2 9JT W Yorkshire England Union Univ Fac Comp Sci RAF Belgrade 11000 Serbia

In this paper we consider the class of simple graphs defined by excluding, as induced subgraphs, even holes (i.e. chordless cycles of even length). These graphs are known as even-hole-free graphs. We prove a decomposition theorem for even-hole-free graphs, that uses star cutsets and 2-joins. This is a significant strengthening of the only other previously known decomposition of even-hole-free graphs, by Conforti, Cornuejols, Kapoor and Vuskovic, that uses 2-joins and star, double star and triple star cutsets. It is also analogous to the decomposition of Berge (i.e. perfect) graphs with skew cutsets, 2-joins and their complements, by Chudnovsky, Robertson, Seymour and Thomas. The similarity between even-hole-free graphs and Berge graphs is higher than the similarity between even-hole-free graphs and simply odd-hole-free graphs, since excluding a 4-hole, automatically excludes all antiholes of length at least 6. In a graph that does not contain a 4-hole, a skew cutset reduces to a star cutset, and a 2-join in the complement implies a star cutset, so in a way it was expected that even-hole-free graphs can be decomposed with just the star cutsets and 2-joins. A consequence of this decomposition theorem is a recognition algorithm for even-hole-free graphs that is significantly faster than the previously known ones. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Even-hole-free graphs Star cutsets 2-joins recognition algorithm Decomposition

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：