Combinatorial Algorithms
31st International Workshop, IWOCA 2020, Bordeaux, France, June 8–10, 2020, Proceedings
Page
%P
-
Chapter and Conference Paper
A Simple Model of Influence: Details and Variants of Dynamics
We consider a simple model of establishing influence in a network. Vertices (people) split into influence groups and follow the opinion of the leader – the influencer – of their group. Groups can merge, based ...
-
Chapter and Conference Paper
A Simple Model of Influence
We propose a simple model of influence in a network, based on edge density. In the model vertices (people) follow the opinion of the group they belong to. The opinion percolates down from an active vertex, the...
-
Article
Selected Papers of the 31st International Workshop on Combinatorial Algorithms, IWOCA 2020
-
Article
Open AccessTime-space trade-offs in population protocols for the majority problem
Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system of n identical agents (finite state machines) performs a global task like electing a unique leader...
-
Book and Conference Proceedings
-
Chapter and Conference Paper
Fair Hitting Sequence Problem: Scheduling Activities with Varied Frequency Requirements
Given a set \(V=\{v_1,\ldots , v_n\}\) of n elements and a family
-
Article
Robustness of the Rotor–Router Mechanism
The rotor–router model, also called the Propp machine, was first considered as a deterministic alternative to the random walk. The edges adjacent to each node v (or equivalently, the exit ports at v) are arranged...
-
Chapter and Conference Paper
Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors)
A garden G is populated by \(n\ge 1\) bamboos ...
-
Chapter and Conference Paper
Fast Consensus for Voting on General Expander Graphs
Distributed voting is a fundamental topic in distributed computing. In the standard model of pull voting, at each step every vertex chooses a neighbour uniformly at random and adopts its opinion. The voting is...
-
Chapter and Conference Paper
Coalescing Walks on Rotor-Router Systems
We consider the rotor-router mechanism for distributing particles in an undirected graph. If the last particle passing through a vertex v took an edge (v,u), then the next time a particle is at v, it will leave v
-
Article
Estimating network parameters using random walks
Sampling from large graphs is an area of great interest, especially since the emergence of huge structures such as Online Social Networks and the World Wide Web (WWW). The large scale properties of a network c...
-
Chapter and Conference Paper
Artificial Neural Networks in the Detection of Known and Unknown DDoS Attacks: Proof-of-Concept
A Distributed Denial of Service attack (DDoS) is designed to overload a target device and its networks with packets to damage its resources or services. This paper proposes an Artificial Neural Network (ANN) d...
-
Chapter and Conference Paper
The Power of Two Choices in Distributed Voting
Distributed voting is a fundamental topic in distributed computing. In pull voting, in each step every vertex chooses a neighbour uniformly at random, and adopts its opinion. The voting is completed when all v...
-
Chapter and Conference Paper
Fast Low-Cost Estimation of Network Properties Using Random Walks
We study the use of random walks as an efficient estimator of global properties of large undirected graphs, for example the number of edges, vertices, triangles, and generally, the number of small fixed subgra...
-
Chapter and Conference Paper
Approximation Bounds on the Number of Mixedcast Rounds in Wireless Ad-Hoc Networks
We consider the following type of Maximum Network Lifetime problems. For a wireless network N with given capacities of node batteries, and a specification of a communication task which is to be performed periodic...
-
Reference Work Entry In depth
Fractional Combinatorial Optimization
This chapter considers combinatorial optimization problems with objective functions in the form of ratios of two functions. A parametric approach to such problems is described and two main general algorithmic ...
-
Chapter and Conference Paper
A Fast Algorithm to Find All High Degree Vertices in Graphs with a Power Law Degree Sequence
We develop a fast method for finding all high degree vertices of a connected graph with a power law degree sequence. The method uses a biassed random walk, where the bias is a function of the power law c of the d...
-
Chapter and Conference Paper
Improved Approximation Bounds for Maximum Lifetime Problems in Wireless Ad-Hoc Network
A wireless ad-hoc network consists of a number of wireless devices (nodes), that communicate with each other within the network using their built-in radio transceivers. The nodes are in general battery-powered...
-
Chapter and Conference Paper
The Cover Times of Random Walks on Hypergraphs
Random walks in graphs have been applied to various network exploration and network maintenance problems. In some applications, however, it may be more natural, and more accurate, to model the underlying netwo...
-
Chapter and Conference Paper
Efficient Connectivity Testing of Hypercubic Networks with Faults
Given a connected graph G and a set F of faulty vertices of G, let G − F be the graph obtained from G by deletion of all vertices of F and edges incident with them. Is there an algorithm, whose running time may b...
