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

Planar median graphs and cubesquare-graphs

DISCRETE APPLIED MATHEMATICS 2023年第1期331卷 38-58页

作者： Seemann, Carsten R. Moulton, Vincent Stadler, Peter F. Hellmuth, Marc Max Planck Inst Math Sci Inselstr 22 D-04103 Leipzig 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 Univ East Anglia Sch Comp Sci Norwich NR4 7TJ England German Ctr Integrat Biodivers Res iDiv Leipzig Germany Competence Ctr Scalable Data Serv & Solut Leipzig Germany Leipzig Res Ctr Civilizat Dis Leipzig Germany Univ Leipzig Ctr Biotechnol & Biomed Hartelstr 16-18 D-04107 Leipzig Germany Univ Vienna Inst Theoret Chem Wahringerstr 17 A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias Bogota Colombia Sanat Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA Stockholm Univ Fac Sci Dept Math SE-10691 Stockholm Sweden

Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. In this paper we provide several novel characterizations of planar median graphs. More specifically, we characterize when a planar graph G is a median graph in terms of forbidden subgraphs and the structure of isometric cycles in G, and also in terms of subgraphs of G that are contained inside and outside of 4-cycles with respect to an arbitrary planar embedding of G. These results lead us to a new characterization of planar median graphs in terms of cubesquare-graphs that is, graphs that can be obtained by starting with cubes and square-graphs, and iteratively replacing 4-cycle boundaries (relative to some embedding) by cubes or square-graphs. As a corollary we also show that a graph is planar median if and only if it can be obtained from cubes and square -graphs by a sequence of "square-boundary"amalgamations. These considerations also lead to an O(n log n)-time recognition algorithm to compute a decomposition of a planar median graph with n vertices into cubes and square-graphs. Crown Copyright (c) 2023 Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Planar median graph Hybercube Square-graph QS-graph Characterization recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast recognition of Fibonacci cubes

引用

algorithmICA 2007年第2期49卷 81-93页

作者： Taranenko, Andrej Vesel, Aleksander Univ Maribor Dept Math & Comp Sci FNM SLO-2000 Maribor Slovenia

Fibonacci cubes are induced subgraphs of hypercubes based on Fibonacci strings. They were introduced to represent interconnection networks as an alternative to the hypercube networks. We derive a characterization of Fibonacci cubes founded on the concept of resonance graphs. The characterization is the basis for an algorithm which recognizes these graphs in O(m log n) time.

关键词： Fibonacci cube resonance graph recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

Generalized Fitch graphs II: Sets of binary relations that are explained by edge-labeled trees

引用

DISCRETE APPLIED MATHEMATICS 2020年 283卷 495-511页

作者： Hellmuth, Marc Seemann, Carsten R. Stadler, Peter F. Ernst Moritz Arndt Univ Greifswald Inst Math & Comp Sci Walther Rathenau Str 47 D-17487 Greifswald Germany Saarland Univ Ctr Bioinformat Bldg E 2-1POB 151150 D-66041 Saarbrucken Germany Max Planck Inst Math Sci Inselstr 22 D-04103 Leipzig 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 Univ Leipzig German Ctr Integrat Biodivers Res iDiv Halle Jena Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Competence Ctr Scalable Data Serv & Solut Dresden Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Leipzig Res Ctr Civilizat Dis Hartelstr 16-18 D-04107 Leipzig Germany Univ Leipzig Ctr Biotechnol & Biomed Hartelstr 16-18 D-04107 Leipzig Germany Univ Vienna Inst Theoret Chem Wahringerstr 17 A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias Sede Bogota Bogota Colombia Santa Fe Inst 1399 Hyde Pk Rd Santa Fe NM 87501 USA

Fitch graphs G = (X, E) are digraphs that are explained by {empty set, 1}-edge-labeled rooted trees T with leaf set X: there is an arc (x, y) is an element of E if and only if the unique path in T that connects the last 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 trees T that are equipped with edge-labeling lambda : E -> P(M) that assigns to each edge a subset M' subset of M of colors. Given such a tree, we can derive a map epsilon((T,lambda)) (or equivalently a set of not necessarily disjoint binary relations), such that i is an element of ((T,lambda))(x, y) (or equivalently (x, y) is an element of R-i) with x, y is an element of X, if and only if there is at least one edge with color i from lca(x, y) to y. The central question considered here: Is a given map epsilon a Fitch map, i.e., is there an edge-labeled tree (T, lambda) with epsilon((T,lambda)) = epsilon, and thus explains epsilon? Here, we provide a characterization of Fitch maps in terms of certain neighborhoods and forbidden submaps. Further restrictions of Fitch maps are considered. Moreover, we show that the least-resolved tree explaining a Fitch map is unique (up to isomorphism). In addition, we provide a polynomial-time algorithm to decide whether epsilon is a Fitch map and, in the affirmative case, to construct the (up to isomorphism) unique least-resolved tree (T*, lambda*) that explains epsilon. (C) 2020 Elsevier B.V. All rights reserved.

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

来源：评论

学校读者我要写书评

暂无评论

Precedence thinness in graphs

引用

DISCRETE APPLIED MATHEMATICS 2022年 323卷 76-95页

作者： Bonomo-Braberman, Flavia Oliveira, Fabiano S. Sampaio Jr, Moyses S. Szwarcfiter, Jayme L. Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Comp Buenos Aires Argentina Univ Buenos Aires CONICET Inst Invest Ciencias Comp ICC Buenos Aires Argentina Univ Estado Rio de Janeiro Rio de Janeiro Brazil Univ Fed Rio de Janeiro Rio de Janeiro Brazil

Interval and proper interval graphs are very well-known graph classes, for which there is a wide literature. As a consequence, some generalizations of interval graphs have been proposed, in which graphs in general are expressed in terms of k interval graphs, by splitting the graph in some special way. As a recent example of such an approach, the classes of k-thin and proper k-thin graphs have been introduced generalizing interval and proper interval graphs, respectively. The complexity of the recognition of each of these classes is still open, even for fixed k >= 2. In this work, we introduce a subclass of k-thin graphs (resp. proper k-thin graphs), called precedence k-thin graphs (resp. precedence proper k-thin graphs). Concerning partitioned precedence k-thin graphs, we present a polynomial time recognition algo-rithm based on PQ trees. With respect to partitioned precedence proper k-thin graphs, we prove that the related recognition problem is NP-complete for an arbitrary k and polynomial-time solvable when k is fixed. Moreover, we present a characterization for these classes based on threshold graphs. (c) 2021 Elsevier B.V. All rights reserved.

关键词： (proper) k-thin graphs Precedence (proper) k-thin graphs recognition algorithm Characterization Threshold graphs

来源：评论

学校读者我要写书评

暂无评论

Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs

引用

THEORETICAL COMPUTER SCIENCE 2015年 602卷 39-49页

作者： Le, Van Bang Oversberg, Andrea Schaudt, Oliver Univ Rostock Inst Informat D-18055 Rostock Germany Univ Cologne Inst Informat D-50931 Cologne Germany

The square of a graph G, denoted G(2), is obtained from G by putting an edge between two distinct vertices whenever their distance is two. Then G is called a square root of G(2). Deciding whether a given graph has a square root is known to be NP-complete, even if the root is required to be a chordal graph or even a split graph. We present a polynomial time algorithm that decides whether a given graph has a Ptolemaic square root. If such a root exists, our algorithm computes one with a minimum number of edges. In the second part of our paper, we give a characterization of the graphs that admit a 3-sun-free split square root. This characterization yields a polynomial time algorithm to decide whether a given graph has such a root, and if so, to compute one. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Square of graph Square of Ptolemaic graph Square of split graph recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

Exploration of head gesture control for hearing instruments

引用

INTERNATIONAL JOURNAL OF AD HOC AND UBIQUITOUS COMPUTING 2014年第4期16卷 240-249页

作者： Tessendorf, Bernd Gravenhorst, Franz Roggen, Daniel Stiefmeier, Thomas Strohrmann, Christina Troester, Gerhard Derleth, Peter Feilner, Manuela ETH Wearable Comp Lab CH-8092 Zurich Switzerland Phonak AG CH-8712 Stafa Switzerland

In this work, we investigated the benefit of head gestures as a user interface to control hearing instruments (HIs). We developed a prototype of a head-gesture-controlled HI, which was based on a customised wireless acceleration sensor for unconstrained and continuous real-time monitoring of the user's head movements. We evaluated the system from a technical point of view and achieved a precision of 96% and a recall of 97% for spotting the two head gestures used: tilting the head to the left and right side. We further evaluated the system from the user's point of view based on the feedback from 6 hearing-impaired HI users (4 men, 2 women, age 27-60). We compared our head-gesture-based control to existing HI user interfaces: HI-integrated buttons and HI remote control. We found that the benefit of the different HI interaction solutions depends on the user's current situations and that all participating HI users would appreciate head gesture control as an additional, complementing user interface.

关键词： multimodal hearing instrument head gesture control user interface recognition algorithm body-worn sensors ubiquitous computing

来源：评论

学校读者我要写书评

暂无评论

Recognizing DNA graphs is difficult

引用

DISCRETE APPLIED MATHEMATICS 2003年第1期127卷 85-94页

作者： Pendavingh, R Schuurman, P Woeginger, GJ Univ Twente Dept Math NL-7500 AE Enschede Netherlands Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands Graz Tech Univ Inst Math A-8010 Graz Austria

DNA graphs are the vertex induced subgraphs of De Bruijn graphs over a four letter alphabet. In this paper, we prove the NP-hardness of various recognition problems for subgraphs of De Bruijn graphs;in particular, the recognition of DNA graphs is shown to be NP-hard. As a consequence, two open questions from a recent paper by Blazewicz et al. (Discrete Appl. Math. 98, (1999) 1) are answered in the negative. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： graph theory recognition algorithm computational complexity NP-hardness De Bruijn graph DNA graphs DNA computing

来源：评论

学校读者我要写书评

暂无评论

algorithms for square-3PC(.,.)-free berge graphs

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2008年第1期22卷 51-71页

作者： Maffray, Frederic Trotignon, Nicolas Vuskovic, Kristina CNRS Lab GSCOP F-38031 Grenoble France Univ Paris 01 Ctr Econ Sorbonne F-75647 Paris 13 France Univ Leeds Sch Comp Leeds LS2 9JT W Yorkshire England

We consider the class of graphs containing no odd hole, no odd antihole, and no configuration consisting of three paths between two nodes such that any two of the paths induce a hole, and at least two of the paths are of length 2. This class generalizes claw-free Berge graphs and square-free Berge graphs. We give a combinatorial algorithm of complexity O(n(7)) to find a clique of maximum weight in such a graph. We also consider several subgraph-detection problems related to this class.

关键词： recognition algorithm maximum weight clique algorithm combinatorial algorithms perfect graphs star decomposition

来源：评论

学校读者我要写书评

暂无评论

Design of computer interactive system for sports training based on artificial intelligence and improved support vector

引用

JOURNAL OF INTELLIGENT & FUZZY SYSTEMS 2019年第5期37卷 6165-6175页

作者： Kong, Fei Wang, Yumin Qingdao Univ Sch Electromechan Engn Dept Ind Design Qingdao Shandong Peoples R China Qingdao Univ Technol Sch Sci Qingdao Shandong Peoples R China

At present, there is less software related to sport technical behavior recognition, and there are few studies on the classification and identification of detailed actions. By introducing computer technology to analyze the efficiency and regularity of sports, not only the characteristics of athletes can be excavated, but also the visibility and dynamic tracking of sport training can be provided. The process of sports education is a fast and complex systematic process. Through the interactive system of physical education, we can use different methods to collect sports data and make a comparative analysis of athletes' movements. Through the data mining of the relationship between athletes' physiological indexes and sports load, the unreasonable link in sports training can be avoided. Also, in sports training, we can use computer vision and modern biomechanics to construct a virtual sports education situation. With the classification accuracy as the fitness function, this paper collects the data through the network database, and returns the corresponding sport training parameters on this basis. The results showed that the accuracy of the model was nearly 98%, which met the actual demand. Therefore, the development of sports education assistant system can provide strong support for the process control of sports training and education.

关键词： Support vector improved model computer interactive system recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

Detecting even holes

引用

JOURNAL OF GRAPH THEORY 2005年第2期48卷 85-111页

作者： Chudnovsky, M Kawarabayashi, K Seymour, P Princeton Univ Dept Math Princeton NJ 08544 USA Tohoku Univ Grad Sch Informat Sci Miyagi 9808579 Japan

Conforti, Cornuejols, Kapoor, and Vuskovic (Even-hole-free graphs. Part II: recognition algorithm, J Graph Theory 40 (2002), 238-266) gave a 73-page polynomial time algorithm to test whether a graph has an induced subgraph that is a cycle of even length. Here, we provide another algorithm to solve the same problem. The differences are: (1) our algorithm is simpler-we are able to search directly for even holes, while the algorithm of Conforti et al. made use of a structure theorem for even-hole-free graphs, proved in an earlier paper (Conforti, Cornuejols, Kapoor, and Vuskovic, Even-hole-free graphs: Part I: Decomposition theorem, J Graph Theory 39 (2002), 6-49);(2) our algorithm is marginally faster-O(n(31)) for an n-vertex graph (and we sketch another more complicated algorithm that runs in time O(n(15))) while the earlier algorithm appears to take about O(n(40));and (3) we can permit 0/1 weights on the edges and look for an induced cycle of even weight. Consequently, we can test whether a graph is "odd signable." (C) 2004 Wiley Periodicals, Inc.

关键词： even hole signed graph recognition algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：