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

2.5-connectivity: Unique components, critical graphs, and applications

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Heinrich, Irene Heller, Till Schmidt, Eva Streicher, Manuel Algorithms and Complexity Group Department of Computer Science Technische Universität Kaiserslautern Kaiserslautern Germany Department of Optimization Fraunhofer ITWM Kaiserslautern Germany Optimization Research Group Department of Mathematics Technische Universität Kaiserslautern Kaiserslautern Germany

If a 2-connected graph stays connected after the removal of an arbitrary vertex and an arbitrary edge, then it is called 2.5-connected. We prove that every 2-connected graph has a canonical decomposition into 2.5-connected components. These components are arranged in a treestructure. We also discuss the connection between 2.5-connected components and triconnected components and use this to present a linear time algorithm which computes the 2.5-connected components of a graph. We show that every critical 2.5-connected graph other than K4 can be obtained from critical 2.5-connected graphs of smaller order using simple graph operations. Furthermore, we demonstrate applications of 2.5-connected components in the context of cycle decompositions and cycle *** Codes 05C40, 05C45, 05C85, 05C75 Copyright © 2020, The Authors. All rights reserved.

关键词： Clustering algorithms

A balance index for phylogenetic trees based on rooted quartets

学校读者我要写书评

暂无评论

arXiv 2018年

作者： Coronado, Tomás M. Mir, Arnau Rosselló, Francesc Valiente, Gabriel Department of Mathematics and Computer Science University of the Balearic Islands PalmaE-07122 Spain Algorithms Bioinformatics Complexity and Formal Methods Research Group Technical University of Catalonia BarcelonaE-08034 Spain

We define a new balance index for rooted phylogenetic trees based on the symmetry of the evolutive history of every set of 4 leaves. This index makes sense for multifurcating trees and it can be computed in time linear in the number of leaves. We determine its maximum and minimum values for arbitrary and bifurcating trees, and we provide exact formulas for its expected value and variance on bifurcating trees under Ford's α-model and Aldous' β-model and on arbitrary trees under the α-γ-model. Copyright © 2018, The Authors. All rights reserved.

关键词： Bifurcation (mathematics)

Strictly-Convex Drawings of 3-Connected Planar Graphs

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Bekos, Michael A. Gronemann, Martin Montecchiani, Fabrizio Symvonis, Antonios Department of Mathematics University of Ioannina Ioannina Greece Algorithms and Complexity Group TU Wien Vienna Austria Department of Engineering University of Perugia Italy School of Applied Mathematical & Physical Sciences NTUA Greece

Strictly-convex straight-line drawings of 3-connected planar graphs in small area form a classical research topic in Graph Drawing. Currently, the best-known area bound for such drawings is O(n2)×O(n2), as shown by Bárány and Rote by means of a sophisticated technique based on perturbing (non-strictly) convex drawings. Unfortunately, the hidden constants in such area bound are in the 104 order. We present a new and easy-to-implement technique that yields strictly-convex straight-line planar drawings of 3-connected planar graphs on an integer grid of size 2(n − 1) × (5n3 − 4n2). Copyright © 2022, The Authors. All rights reserved.

关键词： Drawing (graphics)

On improving approximate solutions by evolutionary algorithms

学校读者我要写书评

暂无评论

On improving approximate solutions by evolutionary algorithm...

Congress on Evolutionary Computation

作者： Tobias Friedrich Jun He Nils Hebbinghaus Frank Neumann Carsten Witt Algorithms and Complexity Group Max Planck Institut für Informatik Saarbruecken Germany School of Computer Science University of Binningham Birmingham UK Fachbereich Informatik LS 2 University of Dortmund Dortmund Germany

Hybrid methods are very popular for solving problems from combinatorial optimization. In contrast to this the theoretical understanding of the interplay of different optimization methods is rare. The aim of this paper is to make a first step into the rigorous analysis of such combinations for combinatorial optimization problems. The subject of our analyses is the vertex cover problem for which several approximation algorithms have been proposed. We point out specific instances where solutions can (or cannot) be improved by the search process of a simple evolutionary algorithm in expected polynomial time.

关键词： Evolutionary computation Approximation algorithms Runtime Optimization methods Polynomials Helium Computer science Algorithm design and analysis Linear programming Sorting

Geometric Planar Networks on Bichromatic Collinear Points

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Bandyapadhyay, Sayan Banik, Aritra Bhore, Sujoy Nöllenburg, Martin Department of Informatics University of Bergen Norway School of Computer Sciences NISER Bhubaneswar India Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group Technische Universität Wien Austria

We study three classical graph problems – Hamiltonian path, minimum spanning tree, and minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. These problems have been widely studied for points in the Euclidean plane, and many of them are NP-hard. In this work, we consider these problems for collinear points. We show that almost all of these problems can be solved in linear time in this setting. © 2019, CC BY.

关键词： Hamiltonians

Noise-induced network topologies

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Folz, Frederic Mehlhorn, Kurt Morigi, Giovanna Theoretische Physik Universität des Saarlandes Saarbrücken66123 Germany Algorithms and Complexity Group Max-Planck-Institut für Informatik Saarland Informatics Campus Saarbrücken66123 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 resonant-like 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. © 2022, CC BY-NC-SA.

关键词： Network topology

On the complexity of the Storyplan Problem

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Binucci, Carla Di Giacomo, Emilio Lenhart, William J. Liotta, Giuseppe Montecchiani, Fabrizio Nöllenburg, Martin Symvonis, Antonios Department of Engineering University of Perugia Italy Department of Computer Science Williams College United States Algorithms and Complexity Group Tu Wien Vienna Austria School of Applied Mathematical & Physical Sciences Ntua Greece

Motivated by dynamic graph visualization, we study the problem of representing a graph G in the form of a storyplan, that is, a sequence of frames with the following properties. Each frame is a planar drawing of the subgraph of G induced by a suitably defined subset of its vertices. Between two consecutive frames, a new vertex appears while some other vertices may disappear, namely those whose incident edges have already been drawn in at least one frame. In a storyplan, each vertex appears and disappears exactly once. For a vertex (edge) visible in a sequence of consecutive frames, the point (curve) representing it does not change throughout the sequence. Note that the order in which the vertices of G appear in the sequence of frames is a total order. In the StoryPlan problem, we are given a graph and we want to decide whether there exists a total order of its vertices for which a storyplan exists. We prove that the problem is NP-complete, and complement this hardness with two parameterized algorithms, one in the vertex cover number and one in the feedback edge set number of G. Also, we prove that partial 3-trees always admit a storyplan, which can be computed in linear time. Finally, we show that the problem remains NP-complete in the case in which the total order of the vertices is given as part of the input and we have to choose how to draw the frames. © 2022, CC BY.

关键词： Hardness

Interplay of periodic dynamics and noise: Insights from a simple adaptive system

学校读者我要写书评

暂无评论

arXiv 2021年

We study the dynamics of a simple adaptive system in the presence of noise and periodic damping. The system is composed by two paths connecting a source and a sink, the dynamics is governed by equations that usually describe food search of the paradigmatic Physarum polycephalum. In this work we assume that the two paths undergo damping whose relative strength is periodically modulated in time and analyse the dynamics in the presence of stochastic forces simulating Gaussian noise. We identify different responses depending on the modulation frequency and on the noise amplitude. At frequencies smaller than the mean dissipation rate, the system tends to switch to the path which minimizes dissipation. Synchronous switching occurs at an optimal noise amplitude which depends on the modulation frequency. This behaviour disappears at larger frequencies, where the dynamics can be described by the time-averaged equations. Here, we find metastable patterns that exhibit the features of noise-induced resonances. © 2021, CC BY-NC-SA.

关键词： Dynamics

Self-organized transport in noisy dynamic networks

学校读者我要写书评

暂无评论

arXiv 2024年

We present a numerical study of multi-commodity transport in a noisy, nonlinear network. The nonlinearity determines the dynamics of the edge capacities, which can be amplified or suppressed depending on the local current flowing across an edge. We consider network self-organization for three different nonlinear functions: For all three we identify parameter regimes where noise leads to self-organization into more robust topologies, that are not found by the sole noiseless dynamics. Moreover, the interplay between noise and specific functional behavior of the nonlinearity gives rise to different features, such as (i) continuous or discontinuous responses to the demand strength and (ii) either single or multi-stable solutions. Our study shows the crucial role of the activation function on noise-assisted phenomena. © 2024, CC BY-NC-SA.

关键词： Nonlinear simulations