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

A spiking neural P system simulator based on CUDA

学校读者我要写书评

暂无评论

A spiking neural P system simulator based on CUDA

12th International Conference on Membrane Computing, CMC 2011

作者： Cabarle, Francis George C. Adorna, Henry Martínez, Miguel A. Algorithms and Complexity Lab. Department of Computer Science University of the Philippines Diliman Diliman 1101 Quezon City Philippines Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Seville Avda. Reina Mercedes s/n 41012 Sevilla Spain

ISBN: (纸本)9783642280238

In this paper we present a Spiking Neural P system (SNP system) simulator based on graphics processing units (GPUs). In particular we implement the simulator using NVIDIA CUDA enabled GPUs. The massively parallel architecture of current GPUs is very suitable for the maximally parallel computations of SNP systems. We simulate a wider variety of SNP systems, after presenting a previous work on SNP system matrix representation which led to their simulation in GPUs, and the simulation algorithm included here. Finally, we compare and present the performance speedups of the CPU-GPU based simulator over the CPU only simulator. © 2012 Springer-Verlag.

关键词： Graphics processing unit

Extending partial 1-planar drawings

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Eiben, Eduard Ganian, Robert Hamm, Thekla Klute, Fabian Nöllenburg, Martin Department of Computer Science Royal Holloway University of London Egham United Kingdom Algorithms and Complexity Group Tu Wien Vienna Australia

Algorithmic extension problems of partial graph representations such as planar graph drawings or geometric intersection representations are of growing interest in topological graph theory and graph drawing. In such an extension problem, we are given a tuple (G,H,H) consisting of a graph G, a connected subgraph H of G and a drawing H of H, and the task is to extend H into a drawing of G while maintaining some desired property of the drawing, such as planarity. In this paper we study the problem of extending partial 1-planar drawings, which are drawings in the plane that allow each edge to have at most one crossing. In addition we consider the subclass of IC-planar drawings, which are 1-planar drawings with independent crossings. Recognizing 1-planar graphs as well as IC-planar graphs is NP-complete and the NP-completeness easily carries over to the extension problem. Therefore, our focus lies on establishing the tractability of such extension problems in a weaker sense than polynomial-Time tractability. Here, we show that both problems are fixed-parameter tractable when parameterized by the number of edges missing from H, i.e., the edge deletion distance between H and G. The second part of the paper then turns to a more powerful parameterization which is based on measuring the vertex+edge deletion distance between the partial and complete drawing, i.e., the minimum number of vertices and edges that need to be deleted to obtain H from G. Copyright © 2020, The Authors. All rights reserved.

关键词： Parameterization

Spiking neural P system simulations on a high performance GPU platform

学校读者我要写书评

暂无评论

Spiking neural P system simulations on a high performance GP...

11th International Conference on algorithms and Architectures for Parallel Processing, ICA3PP 2011

作者： Cabarle, Francis George Adorna, Henry Martínez-Del-Amor, Miguel A. Pérez-Jiménez, Mario J. Algorithms and Complexity Lab. Department of Computer Science University of the Philippines Diliman Quezon City Diliman 1101 Philippines Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Seville Avda. Reina Mercedes s/n Sevilla 41012 Spain

ISBN: (纸本)9783642246685

In this paper we present our results in adapting a Spiking Neural P system (SNP system) simulator to a high performance graphics processing unit (GPU) platform. In particular, we extend our simulations to larger and more complex SNP systems using an NVIDIA Tesla C1060 GPU. The C1060 is manufactured for high performance computing and massively parallel computations, matching the maximally parallel nature of SNP systems. Using our GPU accelerated simulations we present speedups of around 200x for some SNP systems, compared to CPU only simulations. © 2011 Springer-Verlag.

关键词： Graphics processing unit

Noise-Induced Network Topologies

学校读者我要写书评

暂无评论

Physical Review Letters 2023年第26期130卷 267401-267401页

作者： Frederic Folz Kurt Mehlhorn Giovanna Morigi Theoretische Physik Universität des Saarlandes 66123 Saarbrücken Germany Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarland Informatics Campus 66123 Saarbrücken Germany

We analyze transport on a graph with multiple constraints and where the weight of the edges connecting the nodes is a dynamical variable. The network dynamics results from the interplay between a nonlinear function of the flow, dissipation, and Gaussian, additive noise. For a given set of parameters and finite noise amplitudes, the network self-organizes into one of several metastable configurations, according to a probability distribution that depends on the noise amplitude α. At a finite value α, we find a resonantlike behavior for which one network topology is the most probable stationary state. This specific topology maximizes the robustness and transport efficiency, it is reached with the maximal convergence rate, and it is not found by the noiseless dynamics. We argue that this behavior is a manifestation of noise-induced resonances in network self-organization. Our findings show that stochastic dynamics can boost transport on a nonlinear network and, further, suggest a change of paradigm about the role of noise in optimization algorithms.

关键词： Dynamics of networks Biological networks Stochastic dynamical systems Stochastic networks

Lossy kernels for connected dominating set on sparse graphs

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Eiben, Eduard Kumar, Mithilesh Mouawad, Amer E. Panolan, Fahad Siebertz, Sebastian Algorithms and Complexity Group TU Wien Austria Department of Informatics University of Bergen Norway Faculty of Mathematics Informatics and Mechanics University of Warsaw Poland

For α > 1, an α-approximate (bi-)kernel is a polynomial-time algorithm that takes as input an instance (I, k) of a problem Q and outputs an instance (I0, k0) (of a problem Q0) of size bounded by a function of k such that, for every c ≥ 1, a c-approximate solution for the new instance can be turned into a (c · α)-approximate solution of the original instance in polynomial time. This framework of lossy kernelization was recently introduced by Lokshtanov et al. We study Connected Dominating Set (and its distance-r variant) parameterized by solution size on sparse graph classes like biclique-free graphs, classes of bounded expansion, and nowhere dense classes. We prove that for every α > 1, Connected Dominating Set admits a polynomial-size α-approximate (bi-)kernel on all the aforementioned classes. Our results are in sharp contrast to the kernelization complexity of Connected Dominating Set, which is known to not admit a polynomial kernel even on 2-degenerate graphs and graphs of bounded expansion, unless NP ⊆ coNP/poly. We complement our results by the following conditional lower bound. We show that if a class C is somewhere dense and closed under taking subgraphs, then for some value of r ∈ N there cannot exist an α-approximate bi-kernel for the (Connected) Distance-r Dominating Set problem on C for any α > 1 (assuming the Gap Exponential Time Hypothesis). Copyright © 2017, The Authors. All rights reserved.

关键词： Expansion

Near-Tight Runtime Guarantees for Many-Objective Evolutionary algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Wietheger, Simon Doerr, Benjamin Algorithms and Complexity Group Technische Universität Wien Vienna Austria CNRS École Polytechnique Institut Polytechnique de Paris Palaiseau France

Despite significant progress in the field of mathematical runtime analysis of multi-objective evolutionary algorithms (MOEAs), the performance of MOEAs on discrete many-objective problems is little understood. In particular, the few existing bounds for the SEMO, global SEMO, and SMS-EMOA algorithms on classic benchmarks are all roughly quadratic in the size of the Pareto front. In this work, we prove near-tight runtime guarantees for these three algorithms on the four most common benchmark problems OneMinMax, CountingOnesCountingZeros, LeadingOnesTrailingZeros, and OneJumpZeroJump, and this for arbitrary numbers of objectives. Our bounds depend only linearly on the Pareto front size, showing that these MOEAs on these benchmarks cope much better with many objectives than what previous works suggested. Our bounds are tight apart from small polynomial factors in the number of objectives and length of bitstrings. This is the first time that such tight bounds are proven for many-objective uses of these MOEAs. While it is known that such results cannot hold for the NSGA-II, we do show that our bounds, via a recent structural result, transfer to the NSGA-III algorithm. Copyright © 2024, The Authors. All rights reserved.

关键词： Evolutionary algorithms

Exact algorithms for Clustered Planarity with Linear Saturators 35

学校读者我要写书评

暂无评论

Exact Algorithms for Clustered Planarity with Linear Saturat...

35th International Symposium on algorithms and Computation, ISAAC 2024

作者： Da Lozzo, Giordano Ganian, Robert Gupta, Siddharth Mohar, Bojan Ordyniak, Sebastian Zehavi, Meirav Roma Tre University Italy Algorithms and Complexity Group TU Wien Austria BITS Pilani K K Birla Goa Campus India Department of Mathematics Simon Fraser University Burnaby Canada University of Leeds United Kingdom Ben-Gurion University of the Negev Beer-Sheva Israel

ISBN: (纸本)9783959773546

We study Clustered Planarity with Linear Saturators, which is the problem of augmenting an n-vertex planar graph whose vertices are partitioned into independent sets (called clusters) with paths - one for each cluster - that connect all the vertices in each cluster while maintaining planarity. We show that the problem can be solved in time 2O(n) for both the variable and fixed embedding case. Moreover, we show that it can be solved in subexponential time 2O(√n log n) in the fixed embedding case if additionally the input graph is connected. The latter time complexity is tight under the Exponential-Time Hypothesis. We also show that n can be replaced with the vertex cover number of the input graph by providing a linear (resp. polynomial) kernel for the variable-embedding (resp. fixed-embedding) case;these results contrast the NP-hardness of the problem on graphs of bounded treewidth (and even on trees). Finally, we complement known lower bounds for the problem by showing that Clustered Planarity with Linear Saturators is NP-hard even when the number of clusters is at most 3, thus excluding the algorithmic use of the number of clusters as a parameter. © Giordano Da Lozzo, Robert Ganian, Siddharth Gupta, Bojan Mohar, Sebastian Ordyniak, and Meirav Zehavi.

关键词： Graph embeddings

Graphs with Two Moplexes ⁎

学校读者我要写书评

暂无评论

Procedia Computer Science 2021年 195卷 248-256页

作者： Clément Dallard Robert Ganian Meike Hatzel Matjaž Krnc Martin Milanič FAMNIT University of Primorska Koper Slovenia IAM University of Primorska Koper Slovenia Algorithms and Complexity Group TU Wien Vienna Austria LaS Technische Universiät Berlin Berlin Germany

Moplexes are natural graph structures that arise when lifting Dirac’s classical theorem from chordal graphs to general graphs. The notion is known to be closely related to lexicographic searches in graphs as well as to asteroidal triples, and has been applied in several algorithms related to graph classes such as interval graphs, claw-free, and diamond-free graphs. However, while every non-complete graph has at least two moplexes, little is known about structural properties of graphs with a bounded number of moplexes. The study of these graphs is, among others, motivated by the parallel between moplexes in general graphs and simplicial modules in chordal graphs: unlike in the moplex setting, properties of chordal graphs with a bounded number of simplicial modules are well understood. For instance, chordal graphs having at most two simplicial modules are interval. In this work we initiate an investigation of k-moplex graphs, which are defined as graphs containing at most k moplexes. Of particular interest is the smallest nontrivial case, k = 2, which forms a counterpart to the class of interval graphs. As our main structural result, we show that the class of connected 2-moplex graphs is sandwiched between the classes of proper interval graphs and cocomparability graphs; moreover, both inclusions are tight for hereditary classes. From a complexity theoretic viewpoint, this leads to the natural question of whether the presence of at most two moplexes guarantees a sufficient amount of structure to efficiently solve problems that are known to be intractable on cocomparability graphs, but not on proper interval graphs. We develop new reductions that answer this question negatively for two prominent problems fitting this profile, namely Graph Isomorphism and Max-Cut. Furthermore, for graphs with a higher number of moplexes, we lift the previously known result that graphs without asteroidal triples have at most two moplexes to the more general setting of larger asteroidal s

关键词： moplex simplicial vertex avoidable vertex asteroidal number cocomparability graph Hamiltonian path

Enumerating minimal solution sets for metric graph problems

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bergougnoux, Benjamin Defrain, Oscar Inerney, Fionn Mc Institute of Informatics University of Warsaw Poland LIS Aix-Marseille Université France Algorithms and Complexity Group Technische Universität Wien Austria

Problems from metric graph theory like Metric Dimension, Geodetic Set, and Strong Metric Dimension have recently had a strong impact in parameterized complexity by being the first known problems in NP to admit double-exponential lower bounds in the treewidth, and even in the vertex cover number for the latter, assuming the Exponential Time Hypothesis. We initiate the study of enumerating minimal solution sets for these problems and show that they are also of great interest in enumeration. Specifically, we show that enumerating minimal resolving sets in graphs and minimal geodetic sets in split graphs are equivalent to enumerating minimal transversals in hypergraphs (denoted Trans-Enum), whose solvability in total-polynomial time is one of the most important open problems in algorithmic enumeration. This provides two new natural examples to a question that emerged in recent works: for which vertex (or edge) set graph property Π is the enumeration of minimal (or maximal) subsets satisfying Π equivalent to Trans-Enum? As very few properties are known to fit within this context—namely, those related to minimal domination—our results make significant progress in characterizing such properties, and provide new angles to approach Trans-Enum. In contrast, we observe that minimal strong resolving sets can be enumerated with polynomial delay. Additionally, we consider cases where our reductions do not apply, namely graphs with no long induced paths, and show both positive and negative results related to the enumeration and extension of partial solutions. © 2023, CC BY.

关键词： Graph theory