Publications related to Dynamic Balanced Graph Partitioning

Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior

Boi Faltings, Aris Filos Ratsikas, Panayiotis Danassis

We present a novel anytime heuristic (ALMA), inspired by the human principle of altruism, for solving the assignment problem. ALMA is decentralized, completely uncoupled, and requires no communication between the participants. We prove an upper bound on th ...

2019

Finding Perfect Matchings in Bipartite Hypergraphs

Chidambaram Annamalai

Haxell's condition [14] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perf ...

SPRINGER HEIDELBERG2018

Round Compression for Parallel Matching Algorithms

Slobodan Mitrovic, Aleksander Madry

For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture th ...

ASSOC COMPUTING MACHINERY2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Slobodan Mitrovic, Mohsen Ghaffari

We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum ve ...

ASSOC COMPUTING MACHINERY2018

On Computing Breakpoint Distances for Genomes with Duplicate Genes

Bernard Moret, Mingfu Shao

A fundamental problem in comparative genomics is to compute the distance between two genomes in terms of its higher level organization (given by genes or syntenic blocks). For two genomes without duplicate genes, we can easily define (and almost always eff ...

Mary Ann Liebert, Inc2017

Geometric Graph Matching Using Monte Carlo Tree Search

Pascal Fua, Jan Kybic, Miguel Amável Dos Santos Pinheiro

We present an efficient matching method for generalized geometric graphs. Such graphs consist of vertices in space connected by curves and can represent many real world structures such as road networks in remote sensing, or vessel networks in medical imagi ...

Ieee Computer Soc2017

Partial Recovery Bounds for the Sparse Stochastic Block Model

Volkan Cevher, Jonathan Mark Scarlett

In this paper, we study the information-theoretic limits of community detection in the symmetric two-community stochastic block model, with intra-community and inter-community edge probabilities

\frac{a}{n}

and

\frac{b}{n}

respectively. We consider the ...

Ieee2016

Growing a Graph Matching from a Handful of Seeds

Matthias Grossglauser, Seyed Hamed Hassani, Ehsan Kazemi

In many graph–mining problems, two networks from different domains have to be matched. In the absence of reliable node attributes, graph matching has to rely on only the link structures of the two networks, which amounts to a generalization of the classic ...

Assoc Computing Machinery2015

Exponentiality of the exchange algorithm for finding another room-partitioning

Laura Sanità

Let T be a triangulated surface given by the list of vertex-triples of its triangles, called rooms. A room-partitioning for T is a subset R of the rooms such that each vertex of T is in exactly one room in R. Given a room-partitioning R for T, the exchange ...

Elsevier Science Bv2014

Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution

Michel Bierlaire, Bilal Farooq, Dimitrios Efthymiou, Paul Richard Anderson

The generation of synthetic populations through simulation methods is an important research topic and has a key application in agent-based modeling of transport and land use. The next step in this research area is the generation of complete synthetic house ...

Natl Acad Sciences2014

Dynamic Balanced Graph Partitioning

Graph Chatbot

Chat with Graph Search

Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior

Finding Perfect Matchings in Bipartite Hypergraphs

Round Compression for Parallel Matching Algorithms

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

On Computing Breakpoint Distances for Genomes with Duplicate Genes

Geometric Graph Matching Using Monte Carlo Tree Search

Partial Recovery Bounds for the Sparse Stochastic Block Model

Growing a Graph Matching from a Handful of Seeds

Exponentiality of the exchange algorithm for finding another room-partitioning

Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution

Partial Recovery Bounds for the Sparse Stochastic Block Model

On Computing Breakpoint Distances for Genomes with Duplicate Genes

Geometric Graph Matching Using Monte Carlo Tree Search

Round Compression for Parallel Matching Algorithms

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Exponentiality of the exchange algorithm for finding another room-partitioning

Finding Perfect Matchings in Bipartite Hypergraphs

Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior

Association Generation in Synthetic Population for Transportation Applications: Graph-Theoretic Solution

Growing a Graph Matching from a Handful of Seeds