On Vertex Covering Transversal Domination Number of Regular Graphs.
Ontology highlight
ABSTRACT:
SUBMITTER: Vasanthi R
PROVIDER: S-EPMC4828551 | biostudies-other | 2016
REPOSITORIES: biostudies-other
Similar Datasets
Project description:In this paper, we discuss parameterized algorithms for variants of the partial vertex cover problem. Recall that in the classical vertex cover problem (VC), we are given a graph
| S-EPMC7254907 | biostudies-literature
Project description:While Boolean logic has been the backbone of digital information processing, there exist classes of computationally hard problems wherein this paradigm is fundamentally inefficient. Vertex coloring of graphs, belonging to the class of combinatorial optimization, represents one such problem. It is well studied for its applications in data sciences, life sciences, social sciences and technology, and hence, motivates alternate, more efficient non-Boolean pathways towards its solution. Here we demonstrate a coupled relaxation oscillator based dynamical system that exploits insulator-metal transition in Vanadium Dioxide (VO2) to efficiently solve vertex coloring of graphs. Pairwise coupled VO2 oscillator circuits have been analyzed before for basic computing operations, but using complex networks of VO2 oscillators, or any other oscillators, for more complex tasks have been challenging in theory as well as in experiments. The proposed VO2 oscillator network harnesses the natural analogue between optimization problems and energy minimization processes in highly parallel, interconnected dynamical systems to approximate optimal coloring of graphs. We further indicate a fundamental connection between spectral properties of linear dynamical systems and spectral algorithms for graph coloring. Our work not only elucidates a physics-based computing approach but also presents tantalizing opportunities for building customized analog co-processors for solving hard problems efficiently.
| S-EPMC5430425 | biostudies-literature
Project description:Continuous time quantum walks provide an important framework for designing new algorithms and modelling quantum transport and state transfer problems. Often, the graph representing the structure of a problem contains certain symmetries that confine the dynamics to a smaller subspace of the full Hilbert space. In this work, we use invariant subspace methods, that can be computed systematically using the Lanczos algorithm, to obtain the reduced set of states that encompass the dynamics of the problem at hand without the specific knowledge of underlying symmetries. First, we apply this method to obtain new instances of graphs where the spatial quantum search algorithm is optimal: complete graphs with broken links and complete bipartite graphs, in particular, the star graph. These examples show that regularity and high-connectivity are not needed to achieve optimal spatial search. We also show that this method considerably simplifies the calculation of quantum transport efficiencies. Furthermore, we observe improved efficiencies by removing a few links from highly symmetric graphs. Finally, we show that this reduction method also allows us to obtain an upper bound for the fidelity of a single qubit transfer on an XY spin network.
| S-EPMC4557070 | biostudies-literature
Project description:Variable number tandem repeats (VNTRs) are composed of consecutive repetitive DNA with hypervariable repeat count and composition. They include protein coding sequences and associations with clinical disorders. It has been difficult to incorporate VNTR analysis in disease studies that use short-read sequencing because the traditional approach of mapping to the human reference is less effective for repetitive and divergent sequences. In this work, we solve VNTR mapping for short reads with a repeat-pangenome graph (RPGG), a data structure that encodes both the population diversity and repeat structure of VNTR loci from multiple haplotype-resolved assemblies. We develop software to build a RPGG, and use the RPGG to estimate VNTR composition with short reads. We use this to discover VNTRs with length stratified by continental population, and expression quantitative trait loci, indicating that RPGG analysis of VNTRs will be critical for future studies of diversity and disease.
| S-EPMC8275641 | biostudies-literature
Project description:Ionic liquids (ILs) with cyano-functionalized anions are a set of fluids that are still poorly characterized despite their remarkably low viscosities and potential applications. Aiming at providing a comprehensive study on the influence of the number of -CN groups through the surface tension and surface organization of ILs, the surface tensions of imidazolium-based ILs with cyano-functionalized anions were determined at atmospheric pressure and in the (298.15 to 343.15) K temperature range. The ILs investigated are based on 1-alkyl-3-methylimidazolium cations (alkyl = ethyl, butyl and hexyl) combined with the [SCN]-, [N(CN)2]-, [C(CN)3]- and [B(CN)4]-anions. Although the well-known trend regarding the surface tension decrease with the increase of the size of the aliphatic moiety at the cation was observed, the order obtained for the anions is more intricate. For a common cation and at a given temperature, the surface tension decreases according to: [N(CN)2]- > [SCN]- > [C(CN)3]- > [B(CN)4]-. Therefore, the surface tension of this homologous series does not decrease with the increase of the number of -CN groups at the anion as has been previously shown by studies performed with a more limited matrix of ILs. A maximum in the surface tension and critical temperature was observed for [N(CN)2]-based ILs. Furthermore, a minimum in the surface entropy, indicative of a highly structured surface, was found for the same class of ILs. All these evidences seem to be a result of stronger hydrogen-bonding interactions occurring in [N(CN)2]-based ILs, when compared with the remaining CN-based counterparts, and as sustained by cation-anion interaction energies derived from the Conductor Like Screening Model for Real Solvents (COSMO-RS).
| S-EPMC5024756 | biostudies-literature
Project description:A generic degree-4 vertex (4-vertex) origami possesses one continuous degree-of-freedom for rigid folding, and this folding process can be stopped when two of its facets bind together. Such facet-binding will induce self-locking so that the overall structure stays at a pre-specified configuration without additional locking elements or actuators. Self-locking offers many promising properties, such as programmable deformation ranges and piecewise stiffness jumps, that could significantly advance many adaptive structural systems. However, despite its excellent potential, the origami self-locking features have not been well studied, understood, and used. To advance the state of the art, this research conducts a comprehensive investigation on the principles of achieving and harnessing self-locking in 4-vertex origami structures. Especially, for the first time, this study expands the 4-vertex structure construction from single-component to dual-component designs and investigates their self-locking behaviours. By exploiting various tessellation designs, this research discovers that the dual-component designs offer the origami structures with extraordinary attributes that the single-component structures do not have, which include the existence of flat-folded locking planes, programmable locking points and deformability. Finally, proof-of-concept experiments investigate how self-locking can effectively induce piecewise stiffness jumps. The results of this research provide new scientific knowledge and a systematic framework for the design, analysis and utilization of self-locking origami structures for many potential engineering applications.
| S-EPMC5134320 | biostudies-literature
Project description:Mappings of classical computation onto statistical mechanics models have led to remarkable successes in addressing some complex computational problems. However, such mappings display thermodynamic phase transitions that may prevent reaching solution even for easy problems known to be solvable in polynomial time. Here we map universal reversible classical computations onto a planar vertex model that exhibits no bulk classical thermodynamic phase transition, independent of the computational circuit. Within our approach the solution of the computation is encoded in the ground state of the vertex model and its complexity is reflected in the dynamics of the relaxation of the system to its ground state. We use thermal annealing with and without 'learning' to explore typical computational problems. We also construct a mapping of the vertex model into the Chimera architecture of the D-Wave machine, initiating an approach to reversible classical computation based on state-of-the-art implementations of quantum annealing.
| S-EPMC5437300 | biostudies-literature
Project description:Visualizing data through graphs can be an effective way to communicate one's results. A ubiquitous graph and common technique to communicate behavioral data is the bar graph. The bar graph was first invented in 1786 and little has changed in its format. Here, a replacement for the bar graph is proposed. The new format, called a hat graph, maintains some of the critical features of the bar graph such as its discrete elements, but eliminates redundancies that are problematic when the baseline is not at zero. Hat graphs also include design elements based on Gestalt principles of grouping and graph design principles. The effectiveness of the hat graph was tested in five empirical studies. Participants were nearly 40% faster to find and identify the condition that led to the biggest difference from baseline to final test when the data were plotted with hat graphs than with bar graphs. Participants were also more sensitive to the magnitude of an effect plotted with a hat graph compared with a bar graph that was restricted to having its baseline at zero. The recommendation is to use hat graphs when plotting data from discrete categories.
| S-EPMC6694368 | biostudies-literature
Project description:Mycielski graphs are a family of triangle-free graphs
| S-EPMC7326559 | biostudies-literature
Project description:Software test suites based on the concept of interaction testing are very useful for testing software components in an economical way. Test suites of this kind may be created using mathematical objects called covering arrays. A covering array, denoted by CA(N; t, k, v), is an N × k array over [Formula: see text] with the property that every N × t sub-array covers all t-tuples of [Formula: see text] at least once. Covering arrays can be used to test systems in which failures occur as a result of interactions among components or subsystems. They are often used in areas such as hardware Trojan detection, software testing, and network design. Because system testing is expensive, it is critical to reduce the amount of testing required. This paper addresses the Optimal Shortening of Covering ARrays (OSCAR) problem, an optimization problem whose objective is to construct, from an existing covering array matrix of uniform level, an array with dimensions of (N - ?) × (k - ?) such that the number of missing t-tuples is minimized. Two applications of the OSCAR problem are (a) to produce smaller covering arrays from larger ones and (b) to obtain quasi-covering arrays (covering arrays in which the number of missing t-tuples is small) to be used as input to a meta-heuristic algorithm that produces covering arrays. In addition, it is proven that the OSCAR problem is NP-complete, and twelve different algorithms are proposed to solve it. An experiment was performed on 62 problem instances, and the results demonstrate the effectiveness of solving the OSCAR problem to facilitate the construction of new covering arrays.
| S-EPMC5739513 | biostudies-literature