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: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: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:Numerous networks in the real world change with time, producing dynamic graphs such as human mobility networks and brain networks. Typically, the "dynamics on graphs" (e.g., changing node attribute values) are visible, and they may be connected to and suggestive of the "dynamics of graphs" (e.g., evolution of the graph topology). Due to two fundamental obstacles, modeling and mapping between them have not been thoroughly explored: (1) the difficulty of developing a highly adaptable model without solid hypotheses and (2) the ineffectiveness and slowness of processing data with varying granularity. To solve these issues, we offer a novel scalable deep echo-state graph dynamics encoder for networks with significant temporal duration and dimensions. A novel neural architecture search (NAS) technique is then proposed and tailored for the deep echo-state encoder to ensure strong learnability. Extensive experiments on synthetic and actual application data illustrate the proposed method's exceptional effectiveness and efficiency.
| S-EPMC10691542 | biostudies-literature