Publications related to Breadth-first search

Sketches, metrics and fast algorithms

As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in most applications, even storing datasets as acquired has ...

EPFL2022

Cluster-and-Conquer: When Randomness Meets Graph Locality

Anne-Marie Kermarrec, Olivier Ruas

K-Nearest-Neighbors (KNN) graphs are central to many emblematic data mining and machine-learning applications. Some of the most efficient KNN graph algorithms are incremental and local: they start from a random graph, which they incrementally improve by tr ...

IEEE COMPUTER SOC2021

NICEpath: Finding metabolic pathways in large networks through atom-conserving substrate-product pairs

Vassily Hatzimanikatis, Jasmin Maria Hafner

Motivation: Finding biosynthetic pathways is essential for metabolic engineering of organisms to produce chemicals, biodegradation prediction of pollutants and drugs, and for the elucidation of bioproduction pathways of secondary metabolites. A key step in ...

OXFORD UNIV PRESS2021

Full key recovery side-channel attack against ephemeral SIKE on the Cortex-M4

Aymeric Genet, Natacha Yolande Emmanuel Marie Linard de Guertechin, Novak Kaluderovic

This paper describes the first practical single-trace side-channel power analysis of SIKE. While SIKE is a post-quantum key exchange, the scheme still relies on a secret elliptic curve scalar multiplication which involves a loop of a double-and-add procedu ...

2021

Sublinear Algorithms for Spectral Graph Clustering

Aidasadat Mousavifar

This thesis focuses on designing spectral tools for graph clustering in sublinear time. With the emergence of big data, many traditional polynomial time, and even linear time algorithms have become prohibitively expensive. Processing modern datasets requir ...

EPFL2021

Kernel Density Estimation through Density Constrained Near Neighbor Search

Mikhail Kapralov, Navid Nouri

In this paper we revisit the kernel density estimation problem: given a kernel K(x, y) and a dataset of n points in high dimensional Euclidean space, prepare a data structure that can quickly output, given a query q, a (1 + epsilon)-approximation to mu := ...

IEEE2020

Finding Second-Order Stationary Points in Constrained Minimization: A Feasible Direction Approach

Shaul Nadav Hallak

This paper introduces a method for computing points satisfying the second-order necessary optimality conditions for nonconvex minimization problems subject to a closed and convex constraint set. The method comprises two independent steps corresponding to t ...

SPRINGER/PLENUM PUBLISHERS2020

Elastic transactions

Rachid Guerraoui, Vincent Gramoli, Pascal Felber

This paper presents elastic transactions, an appealing alternative to traditional transactions, in particular to implement search structures in shared memory multicore architectures. Upon conflict detection, an elastic transaction might drop what it did so ...

Academic Press Inc Elsevier Science2017

Exact Algorithms for $ L ^{ 1 } $ -TV Regularization of Real-Valued or Circle-Valued Signals

Michaël Unser, Martin Kurt Storath

We consider

L ^{ 1 }

-TV regularization of univariate signals with values on the real line or on the unit circle. While the real data space leads to a convex optimization problem, the problem is nonconvex for circle-valued data. In this paper, we deriv ...

SIAM2016

Exploring Citation Networks to Study Intertextuality in Classics

Matteo Romanello

Referring constitutes such an essential scholarly activity across disciplines that it has been regarded by [Unsworth 2000] as one of the scholarly primitives. In Classics, in particular, the references to passages of the ancient texts - the so-called canon ...

Alliance Digital Humanities Organizations2016

Resting-brain functional connectivity predicted by analytic measures of network communication

Jean-Philippe Thiran, Alessandra Griffa, Patric Hagmann, Olaf Sporns

6 The complex relationship between structural and functional connectivity, as measured by noninvasive imaging of the human brain, poses many unresolved challenges and open questions. Here, we apply analytic measures of network communication to the structur ...

National Academy of Sciences2014

A Branch-and-Price Algorithm to Solve the Integrated Berth Allocation and Yard Assignment Problem in Bulk Ports

Michel Bierlaire, Nitish Umang, Tomas Robenek

In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem ...

Elsevier Science Bv2014

A Distributed Algorithm for Computing the Node Search Number in Trees

Florian Huc

We present a distributed algorithm to compute the node search number in trees. This algorithm extends the centralized algorithm proposed by Ellis et al. (Inf. Comput. 113(1):50-79, 1994). It can be executed in an asynchronous environment, requires an overa ...

2012

A survey and comparison of contemporary algorithms for computing the matrix geometric mean

In this paper we present a survey of various algorithms for computing matrix geometric means and derive new second-order optimization algorithms to compute the Karcher mean. These new algorithms are constructed using the standard definition of the Riemanni ...

2012

Towards Unbiased BFS Sampling

Patrick Thiran, Maciej Kurant

Breadth First Search (BFS) is a widely used approach for sampling large graphs. However, it has been empirically observed that BFS sampling is biased toward high-degree nodes, which may strongly affect the measurement results. In this paper, we quantify an ...

Institute of Electrical and Electronics Engineers2011

A column generation algorithm for the vehicle routing problem with soft time windows

Matteo Salani

The Vehicle Routing Problem with Time Windows consists of computing a minimum cost set of routes for a fleet of vehicles of limited capacity visiting a given set of customers with known demand, with the additional constraint that each customer must be visi ...

2011

Restarts and Nogood Recording in Qualitative Constraint-based Reasoning

Jingshi Li

This paper introduces restart and nogood recording techniques in the domain of qualitative spatial and temporal reasoning. Nogoods and restarts can be applied orthogonally to usual methods for solving qualitative constraint satisfaction problems. In partic ...

2010

Extended Navigability of Small World Networks: Exact Results and New Insights

Paolo De Los Rios, Cécile Caretta Cartozo

Navigability of networks, that is, the ability to find any given destination vertex starting from any other vertex, is crucial to their usefulness. In 2000 Kleinberg showed that optimal navigability could be achieved in small world networks provided that a ...

American Physical Society2009

Elastic Transactions

Rachid Guerraoui, Vincent Gramoli, Pascal Felber

This paper presents elastic transactions, a variant of the transactional model. Upon conflict detection, an elastic transaction might drop what it did so far within a separate transaction that immediately commits, and initiate a new transaction which might ...

Springer2009

A Dynamically Constrained Genetic Algorithm For Hardware-software Partitioning

Pierre-André Mudry, Guillaume Zufferey

In this article, we describe the application of an enhanced genetic algorithm to the problem of hardware-software codesign. Starting from a source code written in a high-level language our algorithm determines, using a dynamically-weighted fitness function ...

Association for Computing Machinery2006