BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Laurent Viennot

Laurent Viennot appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Networking and Internet ArchitectureData Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingSocial and Information NetworksComputer Science and Game TheoryDiscrete Mathematicsphysics.soc-ph

Catalog footprint

What is connected

7works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

7 published item(s)

preprint2021arXiv

On Computing Pareto Optimal Paths in Weighted Time-Dependent Networks

A weighted point-availability time-dependent network is a list of temporal edges, where each temporal edge has an appearing time value, a travel time value, and a cost value. In this paper we consider the single source Pareto problem in weighted point-availability time-dependent networks, which consists of computing, for any destination d, all Pareto optimal pairs (t, c), where t and c are the arrival time and the cost of a path from s to d, respectively (a pair (t, c) is Pareto optimal if there is no path with arrival time smaller than t and cost no worse than c or arrival time no greater than t and better cost). We design and analyse a general algorithm for solving this problem, whose time complexity is O(M log P), where M is the number of temporal edges and P is the maximum number of Pareto optimal pairs for each node of the network. This complexity significantly improves the time complexity of the previously known solution. Our algorithm can be used to solve several different minimum cost path problems in weighted point-availability time-dependent networks with a vast variety of cost definitions, and it can be easily modified in order to deal with the single destination Pareto problem. All our results apply to directed networks, but they can be easily adapted to undirected networks with no edges with zero travel time.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons

The goal of a hub-based distance labeling scheme for a network G = (V, E) is to assign a small subset S(u) $\subseteq$ V to each node u $\in$ V, in such a way that for any pair of nodes u, v, the intersection of hub sets S(u) $\cap$ S(v) contains a node on the shortest uv-path. The existence of small hub sets, and consequently efficient shortest path processing algorithms, for road networks is an empirical observation. A theoretical explanation for this phenomenon was proposed by Abraham et al. (SODA 2010) through a network parameter they called highway dimension, which captures the size of a hitting set for a collection of shortest paths of length at least r intersecting a given ball of radius 2r. In this work, we revisit this explanation, introducing a more tractable (and directly comparable) parameter based solely on the structure of shortest-path spanning trees, which we call skeleton dimension. We show that skeleton dimension admits an intuitive definition for both directed and undirected graphs, provides a way of computing labels more efficiently than by using highway dimension, and leads to comparable or stronger theoretical bounds on hub set size.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Forwarding Tables Verification through Representative Header Sets

Forwarding table verification consists in checking the distributed data-structure resulting from the forwarding tables of a network. A classical concern is the detection of loops. We study this problem in the context of software-defined networking (SDN) where forwarding rules can be arbitrary bitmasks (generalizing prefix matching) and where tables are updated by a centralized controller. Basic verification problems such as loop detection are NP-hard and most previous work solves them with heuristics or SAT solvers. We follow a different approach based on computing a representation of the header classes, i.e. the sets of headers that match the same rules. This representation consists in a collection of representative header sets, at least one for each class, and can be computed centrally in time which is polynomial in the number of classes. Classical verification tasks can then be trivially solved by checking each representative header set. In general, the number of header classes can increase exponentially with header length, but it remains polynomial in the number of rules in the practical case where rules are constituted with predefined fields where exact, prefix matching or range matching is applied in each field (e.g., IP/MAC addresses, TCP/UDP ports). We propose general techniques that work in polynomial time as long as the number of classes of headers is polynomial and that do not make specific assumptions about the structure of the sets associated to rules. The efficiency of our method rely on the fact that the data-structure representing rules allows efficient computation of intersection, cardinal and inclusion. Finally, we propose an algorithm to maintain such representation in presence of updates (i.e., rule insert/update/removal). We also provide a local distributed algorithm for checking the absence of black-holes and a proof labeling scheme for locally checking the absence of loops.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

LiveRank: How to Refresh Old Datasets

This paper considers the problem of refreshing a dataset. More precisely , given a collection of nodes gathered at some time (Web pages, users from an online social network) along with some structure (hyperlinks, social relationships), we want to identify a significant fraction of the nodes that still exist at present time. The liveness of an old node can be tested through an online query at present time. We call LiveRank a ranking of the old pages so that active nodes are more likely to appear first. The quality of a LiveRank is measured by the number of queries necessary to identify a given fraction of the active nodes when using the LiveRank order. We study different scenarios from a static setting where the Liv-eRank is computed before any query is made, to dynamic settings where the LiveRank can be updated as queries are processed. Our results show that building on the PageRank can lead to efficient LiveRanks, for Web graphs as well as for online social networks.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Self-Organizing Flows in Social Networks

Social networks offer users new means of accessing information, essentially relying on "social filtering", i.e. propagation and filtering of information by social contacts. The sheer amount of data flowing in these networks, combined with the limited budget of attention of each user, makes it difficult to ensure that social filtering brings relevant content to the interested users. Our motivation in this paper is to measure to what extent self-organization of the social network results in efficient social filtering. To this end we introduce flow games, a simple abstraction that models network formation under selfish user dynamics, featuring user-specific interests and budget of attention. In the context of homogeneous user interests, we show that selfish dynamics converge to a stable network structure (namely a pure Nash equilibrium) with close-to-optimal information dissemination. We show in contrast, for the more realistic case of heterogeneous interests, that convergence, if it occurs, may lead to information dissemination that can be arbitrarily inefficient, as captured by an unbounded "price of anarchy". Nevertheless the situation differs when users' interests exhibit a particular structure, captured by a metric space with low doubling dimension. In that case, natural autonomous dynamics converge to a stable configuration. Moreover, users obtain all the information of interest to them in the corresponding dissemination, provided their budget of attention is logarithmic in the size of their interest set.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Toward more localized local algorithms: removing assumptions concerning global knowledge

Numerous sophisticated local algorithm were suggested in the literature for various fundamental problems. Notable examples are the MIS and $(Δ+1)$-coloring algorithms by Barenboim and Elkin [6], by Kuhn [22], and by Panconesi and Srinivasan [34], as well as the $O(Δ2)$-coloring algorithm by Linial [28]. Unfortunately, most known local algorithms (including, in particular, the aforementioned algorithms) are non-uniform, that is, local algorithms generally use good estimations of one or more global parameters of the network, e.g., the maximum degree $Δ$ or the number of nodes n. This paper provides a method for transforming a non-uniform local algorithm into a uniform one. Furthermore , the resulting algorithm enjoys the same asymp-totic running time as the original non-uniform algorithm. Our method applies to a wide family of both deterministic and randomized algorithms. Specifically, it applies to almost all state of the art non-uniform algorithms for MIS and Maximal Matching, as well as to many results concerning the coloring problem. (In particular, it applies to all aforementioned algorithms.) To obtain our transformations we introduce a new distributed tool called pruning algorithms, which we believe may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Node-Disjoint Multipath Spanners and their Relationship with Fault-Tolerant Spanners

Motivated by multipath routing, we introduce a multi-connected variant of spanners. For that purpose we introduce the $p$-multipath cost between two nodes $u$ and $v$ as the minimum weight of a collection of $p$ internally vertex-disjoint paths between $u$ and $v$. Given a weighted graph $G$, a subgraph $H$ is a $p$-multipath $s$-spanner if for all $u,v$, the $p$-multipath cost between $u$ and $v$ in $H$ is at most $s$ times the $p$-multipath cost in $G$. The $s$ factor is called the stretch. Building upon recent results on fault-tolerant spanners, we show how to build $p$-multipath spanners of constant stretch and of $\tO(n^{1+1/k})$ edges, for fixed parameters $p$ and $k$, $n$ being the number of nodes of the graph. Such spanners can be constructed by a distributed algorithm running in $O(k)$ rounds. Additionally, we give an improved construction for the case $p=k=2$. Our spanner $H$ has $O(n^{3/2})$ edges and the $p$-multipath cost in $H$ between any two node is at most twice the corresponding one in $G$ plus $O(W)$, $W$ being the maximum edge weight.

0 citations0 reviewsNo code linkedOpen access