Results 31 to 40 of about 165,258 (315)
Scientific Reports, 2021 Whenever some phenomenon can be represented as a graph or a network it seems pertinent to explore how much the mathematical properties of that network impact the phenomenon. In this study we explore the same philosophy in the context of immunology.
Arindam Banerjee +2 more
doaj +1 more source
Vertex Cover Reconfiguration and Beyond
Algorithms, 2018 In the Vertex Cover Reconfiguration (VCR) problem, given a graph G, positive integers k and ℓ and two vertex covers S and T of G of size at most k, we determine whether S can be transformed into T by a sequence of at most ℓ vertex additions or removals ...
Amer E. Mouawad +3 more
doaj +1 more source
Generalization of the Cover Pebbling Number for Networks
Frontiers in Physics, 2020 Pebbling can be viewed as a model of resource transportation for networks. We use a graph to denote the network. A pebbling move on a graph consists of the removal of two pebbles from a vertex and the placement of one pebble on an adjacent vertex.
Zheng-Jiang Xia, Zhen-Mu Hong
doaj +1 more source
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover [PDF]
, 2002 Given a $k$-uniform hyper-graph, the E$k$-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyper-edge. We present a new multilayered PCP construction that extends the Raz verifier.
Dinur, Irit +3 more
core +4 more sources
Dynamic monopolies in simple graphs [PDF]
AUT Journal of Mathematics and ComputingThis paper studies a repetitive polling game played on an $n$-vertex graph $G$. At first, each vertex is colored, Black or White. At each round, each vertex (simultaneously) recolors itself by the color of the majority of its closed neighborhood.
Leila Musavizadeh Jazaeri +1 more
doaj +1 more source
Reconfiguring k-path Vertex Covers [PDF]
, 2020 29 pages, 4 figures, to appear in WALCOM ...
Duc A. Hoang +2 more
openaire +2 more sources
Determining the Solution Space of Vertex-Cover by Interactions and Backbones [PDF]
, 2012 To solve the combinatorial optimization problems especially the minimal Vertex-cover problem with high efficiency, is a significant task in theoretical computer science and many other subjects.
B. Bollobàs +12 more
core +1 more source
The distinguishing number and the distinguishing index of line and graphoidal graph(s)
AKCE International Journal of Graphs and Combinatorics, 2020 The distinguishing number (index) () of a graph is the least integer such that has a vertex labeling (edge labeling) with labels that is preserved only by a trivial automorphism.
Saeid Alikhani, Samaneh Soltani
doaj +1 more source
Parameterized Power Vertex Cover [PDF]
Discrete Mathematics & Theoretical Computer Science, 2016 We study a recently introduced generalization of the Vertex Cover (VC) problem, called Power Vertex Cover (PVC). In this problem, each edge of the input graph is supplied with a positive integer demand. A solution is an assignment of (power) values to the vertices, so that for each edge one of its endpoints has value as high as the demand, and the ...
Angel, Eric +3 more
openaire +3 more sources
Combinatorial Dominance Guarantees for Heuristic Algorithms [PDF]
Discrete Mathematics & Theoretical Computer Science, 2007 An $f(n)$ $\textit{dominance bound}$ on a heuristic for some problem is a guarantee that the heuristic always returns a solution not worse than at least $f(n)$ solutions.
Daniel Berend +2 more
doaj +1 more source