An algorithm for computing the k-convex closure of a subgraph relative to a given equivalence relation R among edges of a graph is given. For general graph and arbitrary relation R the time complexity is O(qn(2) + mn)...
详细信息
An algorithm for computing the k-convex closure of a subgraph relative to a given equivalence relation R among edges of a graph is given. For general graph and arbitrary relation R the time complexity is O(qn(2) + mn), where n is the number of vertices, m is the number of edges and q is the number of equivalence classes of R. A special case is an O(mn) algorithm for the usual k-convexity. We also show that Cartesian graph bundles over triangle free bases can be recognized in O(mn) time and that all representations of such graphs as Cartesian graph bundles can be found in O(mn(2)) time.
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 F...
详细信息
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.
作者:
Hellmuth, MarcSeemann, 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 la...
详细信息
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.
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...
详细信息
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.
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 s...
详细信息
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.
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 a...
详细信息
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.
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...
详细信息
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.
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...
详细信息
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.
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...
详细信息
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.
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 sub...
详细信息
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.
暂无评论