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

DISCRETE MATHEMATICS 2003年第1-3期268卷 129-137页

作者： Eschen, EM Klostermeyer, WF Sritharan, R W Virginia Univ Lane Dept Comp Sci & Elect Engn Morgantown WV 26506 USA Univ N Florida Jacksonville FL 32224 USA Univ Dayton Dept Comp Sci Dayton OH 45469 USA

A graph G is a domination graph if each induced subgraph of G has a pair of vertices such that the open neighborhood of one is contained in the closed neighborhood of the other in the subgraph. No polynomial time algorithm or hardness result is known for the problem of deciding whether a graph is a domination graph. In this paper, it is shown that the class of planar domination graphs is equivalent to the class of planar weakly chordal graphs, and thus, can be recognized in polynomial time. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： planar graph weakly chordal graph domination graph recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

Ptolemaic and Chordal Cover-Incomparability Graphs

引用

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS 2022年第1期39卷 29-43页

作者： Anil, Arun Changat, Manoj Univ Kerala Dept Futures Studies Thiruvananthapuram 695581 Kerala India

Cover-incomparability graphs (C-I graphs) are graphs whose edge-set is the union of edge-sets of the incomparability graph and the cover graph of some poset. C-I graphs captured attention as an interesting class of graphs from posets. It is known that the recognition of C-I graphs is NP-complete (Maxova et al., Order 26(3), 229-236, 2009). Hence, the problem of finding a particular graph family of C-I graphs whose recognition complexity is polynomial is interesting. We present a new forbidden subgraph characterization of Ptolemaic C-I graphs and a linear time algorithm for its recognition. The characterization of chordal C-I graph is an unsolved problem in this area for quite some time. In this paper, we characterize the family of chordal C-I graphs.

关键词： C-I graphs Ptolemaic Chordal graphs recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

ON THE CHAIN CODE OF A LINE

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 1982年第3期4卷 347-353页

作者： WU, LD BROWN UNIV DIV APPL MATHPROVIDENCERI 02912

In 1970 Freeman suggested the following criteria which the chain code of a line must meet [1], [2]: 1) at most two basic directions are present and these can differ only by unity, modulo eight, 2) one of these values always occurs singly, 3) successive occurrences of the principal direction occurring singly are as uniformly spaced as possible. In this correspondence we give the following: 1) an algorithm presentation of Freeman"s three properties about the chain code of a line and the proof that it is also the algorithm recognizing whether a chain code is the chain code of a line, 2) the proof of the equivalence of the above presentation and Rosenfeld"s chord property [3].

关键词： Shape algorithm design and analysis Pattern recognition Image analysis Mathematics Computer science Author Keywords straight line Chain code chord property generating algorithm recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

The mathematics of xenology: di-cographs, symbolic ultrametrics, 2-structures and tree-representable systems of binary relations

引用

JOURNAL OF MATHEMATICAL BIOLOGY 2017年第1期75卷 199-237页

作者： Hellmuth, Marc Stadler, Peter F. Wieseke, Nicolas Ernst Moritz Arndt Univ Greifswald Dept Math & Comp Sci Walther Rathenau Str 47 D-17487 Greifswald Germany Univ Saarland Ctr Bioinformat Bldg E 2-1POB 151150 D-66041 Saarbrucken Germany Univ Leipzig Dept Comp Sci Bioinformat Grp Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Hartelstr 16-18 D-04107 Leipzig Germany Max Planck Inst Math Sci Inselstr 22 D-04103 Leipzig Germany Univ Vienna Inst Theoret Chem Wahringerstr 17 A-1090 Vienna Austria Santa Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA Univ Leipzig Dept Comp Sci Parallel Comp & Complex Syst Grp Johannisgasse 26 D-04103 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Johannisgasse 26 D-04103 Leipzig Germany

The concepts of orthology, paralogy, and xenology play a key role in molecular evolution. Orthology and paralogy distinguish whether a pair of genes originated by speciation or duplication. The corresponding binary relations on a set of genes form complementary cographs. Allowing more than two types of ancestral event types leads to symmetric symbolic ultrametrics. Horizontal gene transfer, which leads to xenologous gene pairs, however, is inherent asymmetric since one offspring copy "jumps" into another genome, while the other continues to be inherited vertically. We therefore explore here the mathematical structure of the non-symmetric generalization of symbolic ultrametrics. Our main results tie non-symmetric ultrametrics together with di-cographs (the directed generalization of cographs), so-called uniformly non-prime () 2-structures, and hierarchical structures on the set of strong modules. This yields a characterization of relation structures that can be explained in terms of trees and types of ancestral events. This framework accommodates a horizontal-transfer relation in terms of an ancestral event and thus, is slightly different from the the most commonly used definition of xenology. As a first step towards a practical use, we present a simple polynomial-time recognition algorithm of 2-structures and investigate the computational complexity of several types of editing problems for 2-structures. We show, finally that these NP-complete problems can be solved exactly as Integer Linear Programs.

关键词： Xenologs Paralogs Orthologs Gene tree 2-Structures Uniformly non-prime decomposition Di-cograph Symbolic ultrametric recognition algorithm NP-completeness Integer Linear Program

来源：评论

学校读者我要写书评

暂无评论

On the canonical metric representation, average distance, and partial Hamming graphs

引用

EUROPEAN JOURNAL OF COMBINATORICS 2006年第1期27卷 68-73页

作者： Klavzar, S Univ Maribor Dept Math & Comp Sci PeF SLO-2000 Maribor Slovenia

Average distance of a graph is expressed in terms of its canonical metric representation. The equality can be modified to an inequality in such a way that it characterizes isometric subgraphs of Hamming graphs. This approach simplifies recognition of these graphs and computation of their average distance. (c) 2004 Elsevier Ltd. All rights reserved.

关键词： canonical metric representation Hamming graphs partial hamming graphs Wiener index recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

A note on the recognition of bisplit graphs

引用

DISCRETE MATHEMATICS 2006年第17期306卷 2108-2110页

作者： Abueida, Atif Sritharan, R. Univ Dayton Dept Comp Sci Dayton OH 45469 USA Univ Dayton Dept Math Dayton OH 45469 USA

We show that bisplit graphs can be recognized in O(n(2)) time. The previous best bound of O(mn) for the problem appeared in a recently published article [A. Brandstadt, P.L. Hammer, V.B. Le, V.V. Lozin, Bisplit graphs... 详细信息

关键词： bisplit graphs 3-colorable graphs recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

Generalized Fitch graphs: Edge-labeled graphs that are explained by edge-labeled trees

引用

DISCRETE APPLIED MATHEMATICS 2019年 267卷 1-11页

作者： Hellmuth, Marc Ernst Moritz Arndt Univ Greifswald Dept Math & Comp Sci Walther Rathenau Str 47 D-17487 Greifswald Germany Saarland Univ Ctr Bioinformat Bldg E 2-1POB 151150 D-66041 Saarbrucken Germany

Fitch graphs G = (X, E) are di-graphs that are explained by {circle times, 1}-edge-labeled rooted trees with leaf set X: there is an arc xy is an element of E if and only if the unique path in T that connects the least common ancestor lca(x, y) of x and y with y contains at least one edge with label "1". In practice, Fitch graphs represent xenology relations, i.e., pairs of genes x and y for which a horizontal gene transfer happened along the path from lca(x, y) to y. In this contribution, we generalize the concept of Fitch graphs and consider complete di-graphs K-vertical bar x vertical bar with vertex set X and a map e that assigns to each arc xy a unique label epsilon(x, y) is an element of M boolean OR {circle times}, where M denotes an arbitrary set of symbols. A di-graph (K-vertical bar x vertical bar, epsilon) is a generalized Fitch graph if there is an M boolean OR {circle times}-edge-labeled tree (T, lambda) that can explain (K-vertical bar x vertical bar, epsilon). We provide a simple characterization of generalized Fitch graphs (K-vertical bar x vertical bar, epsilon) and give an O(vertical bar x vertical bar(2))-time algorithm for their recognition as well as for the reconstruction of the unique least-resolved phylogenetic tree that explains (K-vertical bar x vertical bar, epsilon). (C) 2019 Elsevier B.V. All rights reserved.

关键词： Labeled trees Forbidden subgraphs Phylogenetics Xenology Fitch graph recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

Compatibility of partitions with trees, hierarchies, and split systems

引用

DISCRETE APPLIED MATHEMATICS 2022年 314卷 265-283页

作者： Hellmuth, Marc Schaller, David Stadler, Peter F. Stockholm Univ Fac Sci Dept Math SE-10691 Stockholm Sweden Univ Leipzig Dept Comp Sci Bioinformat Grp Hartelstr 1618 D-04107 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Hartelstr 1618 D-04107 Leipzig Germany Max Planck Inst Math Sci Inselstr 22 D-04103 Leipzig Germany Univ Vienna Dept Theoret Chem Wahringerstr 17 A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias Bogota Colombia Santa Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA

The question whether a partition P and a hierarchy H or a tree-like split system S are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether the sets of P coincide with leaf sets of connected components obtained by deleting some edges from the tree T that represents H or S, respectively. More generally, we ask whether a refinement T* of T exists such that T* and P are compatible in this sense. The latter is closely related to the question as to whether there exists a tree at all that is compatible with P. We report several characterizations for (refinements of) hierarchies and split systems that are compatible with (systems of) partitions. In addition, we provide a linear-time algorithm to check whether refinements of trees and a given partition are compatible. The latter problem becomes NP-complete but fixed-parameter tractable if a system of partitions is considered instead of a single partition. In this context, we also explore the close relationship of the concept of compatibility and so-called Fitch maps. (C) 2022 The Author(s). Published by Elsevier B.V.

关键词： Hierarchy Split system Phylogenetic tree Partition Compatibility recognition algorithm Fitch map

来源：评论

学校读者我要写书评

暂无评论

Finding a Sun in Building-Free Graphs

引用

GRAPHS AND COMBINATORICS 2012年第3期28卷 347-364页

作者： 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 Sci 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

Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete (HoA ng in SIAM J Discret Math 23:2156-2162, 2010). We show that whether a building-free graph contains a sun can be decided in O(min{mn (3), m (1.5) n (2)}) time and, if a sun exists, it can be found in the same time bound. The class of building-free graphs contains many interesting classes of perfect graphs such as Meyniel graphs which, in turn, contains classes such as hhd-free graphs, i-triangulated graphs, and parity graphs. Moreover, there are imperfect graphs that are building-free. The class of building-free graphs generalizes several classes of graphs for which an efficient test for the presence of a sun is known. We also present a vertex elimination scheme for the class of (building, gem)-free graphs. The class of (building, gem)-free graphs is a generalization of the class of distance hereditary graphs and a restriction of the class of (building, sun)-free graphs.

关键词： Graph recognition algorithm Building-free (Building sun)-free (Building gem)-free Distance hereditary

来源：评论

学校读者我要写书评

暂无评论

The recognition of geodetically connected graphs

引用

INFORMATION PROCESSING LETTERS 1998年第2期65卷 81-88页

作者： Chang, JM Ho, CW Natl Cent Univ Inst Comp Sci & Informat Engn Chungli 32054 Taiwan Natl Taipei Coll Business Dept Informat Management Taipei 10021 Taiwan

Let G = (V,E) be a graph with vertex set V of size n and edge set E of size m. A vertex nu is an element of V is called a hinge vertex if the distance of any two vertices becomes longer after ii is removed. A graph without hinge vertex is called a hinge-free graph. In general, a graph G is k-geodetically connected or k-GC for shea if G can tolerate any k-1 vertices failures without increasing the distance among all the remaining vertices. In this paper, we show that recognizing a graph G to be k-GC for the largest value of k can be solved in O(nm) time. In addition, more efficient algorithms for recognizing the L-GC property on some special graphs are presented. These include the O(n + m) time algorithms on strongly chordal graphs (if a strong elimination ordering is given), ptolemaic graphs, and interval graphs, and an O(n(2)) time algorithm on undirected path graphs (if a characteristic tree model is given). Moreover, we show that if the input graph G is not hinge-free then finding all hinge vertices of G can be solved in the same time complexity on the above classes of graphs. (C) 1998 Elsevier Science B.V.

关键词： hinge vertices geodetically connected recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：