Metric dimension of critical Galton–Watson trees and linear preferential attachment trees

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the ...

The design and implementation of efficient concurrent data structures has seen significant attention. However, most of this work has focused on concurrent data structures providing good worst-case guarantees, although, in real workloads, objects are often ...

Car sharing systems (CSSs) are one of the environmentally beneficial solutions in urban transportation. However, the operators still struggle to make these systems profitable. One of the main contributors in operational cost is rebalancing operations. Ther ...

In this thesis, we investigate the inverse problem of trees and barcodes from a combinatorial, geometric, probabilistic and statistical point of view. Computing the persistent homology of a merge tree yields a barcode B. Reconstructing a tree from B invol ...

The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to t ...

In the localization game on a graph, the goal is to find a fixed but unknown target node v* with the least number of distance queries possible. In the j-th step of the game, the player queries a single node v_j and receives, as an answer to their query, th ...

Decision trees have been widely used as classifiers in many machine learning applications thanks to their lightweight and interpretable decision process. This paper introduces Tree in Tree decision graph (TnT), a framework that extends the conventional dec ...

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...

This article introduces a new class of models for multiple networks. The core idea is to parameterize a distribution on labeled graphs in terms of a Frechet mean graph (which depends on a user-specified choice of metric or graph distance) and a parameter t ...

Suppose we have randomized decision trees for an outer function f and an inner function g. The natural approach for obtaining a randomized decision tree for the composed function (f∘ gⁿ)(x¹,…,xⁿ) = f(g(x¹),…,g(xⁿ)) involves amplifying the success probabili ...

We propose an online algorithm for sequential learning in the contextual multiarmed bandit setting. Our approach is to partition the context space and, then, optimally combine all of the possible mappings between the partition regions and the set of bandit ...

Lexicographic Boolean satisfiability (LEXSAT) is a variation of the Boolean satisfiability problem (SAT). Given a variable order, LEXSAT finds a satisfying assignment whose integer value under the given variable order is minimum (maximum) among all satisfi ...

We consider learning of fundamental properties of communities in large noisy networks, in the prototypical situation where the nodes or users are split into two classes according to a binary property, e.g., according to their opinions or preferences on a t ...

We study the extinction time tau of the contact process started with full occupancy on finite trees of bounded degree. We show that, if the infection rate is larger than the critical rate for the contact process on Z, then, uniformly over all trees of degr ...

A straight-line drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph G, (cr) over bar (G), is the mi ...

Silicon and oxygen are potential light elements in Earth's core because their stronger affinity to metal observed with increasing temperature posits that significant amounts of both can be incorporated into the core. It was proposed that an Fe-Si-O liquid ...

An open problem in polarization theory is to determine the binary operations that always lead to polarization (in the general multilevel sense) when they are used in Arikan style constructions. This paper, which is presented in two parts, solves this probl ...

We consider the variation of Ramsey numbers introduced by Erdos and Pach [J. Graph Theory, 7 (1983), pp. 137-147], where instead of seeking complete or independent sets we only seek a t-homogeneous set, a vertex subset that induces a subgraph of minimum de ...

A Digital Pixel Sensor (DPS) based CMOS camera configured to record frames and comprising an event detection sensor configured to look for an event happening in a determined frame, comprising an array of event detection pixels, a first reference voltage ge ...

Metric dimension of critical Galton–Watson trees and linear preferential attachment trees

Chattez avec Graph Search

Fairness and Explainability in Clustering Problems

The splay-list: a distribution-adaptive concurrent skip-list

A general framework to evaluate different rebalancing operations strategies in one-way car sharing systems

From Trees to Barcodes and Back Again: A Combinatorial, Probabilistic and Geometric Study of a Topological Inverse Problem

On the robustness of the metric dimension of grid graphs to adding a single edge

Sequential metric dimension for random graphs

Tree in Tree: from Decision trees to Decision Graphs

Adaptive majority problems for restricted query graphs and for weighted sets

Modeling Network Populations via Graph Distances

When Is Amplification Necessary for Composition in Randomized Query Complexity?

Asymptotically Optimal Contextual Bandit Algorithm Using Hierarchical Structures

Fast generation of lexicographic satisfiable assignments: enabling canonicity in SAT-based applications

Unsupervised Robust Nonparametric Learning Of Hidden Community Properties

Exponential extinction time of the contact process on finite graphs

Approximating the rectilinear crossing number

Ab Initio Molecular Dynamics Investigation of Molten Fe-Si-O in Earth's Core

An Ergodic Theory of Binary Operations-Part I: Key Properties

A Precise Threshold For Quasi-Ramsey Numbers

Adaptive Majority Problems For Restricted Query Graphs And For Weighted Sets

A novel cmos image sensor with event/change detection and reduced data redundancy