Publications associées à Sommet (géométrie)

Absolute energy levels of liquid water from many-body perturbation theory with effective vertex corrections

Alfredo Pasquarello, Thomas Bischoff, Aleksei Tal

We demonstrate the importance of addressing the F vertex and thus going beyond the GW approximation for achieving the energy levels of liquid water in manybody perturbation theory. In particular, we consider an effective vertex function in both the polariz ...

National Academy of Sciences2024

Vertex function compliant with the Ward identity for quasiparticle self-consistent calculations beyond GW

Alfredo Pasquarello, Aleksei Tal, Wei Chen

We extend the quasiparticle self-consistent approach beyond the GW approximation by using a range separated vertex function. The developed approach yields band gaps, dielectric constants, and band positions with an accuracy similar to highest-level electro ...

2021

How to Match in Modern Computational Settings

Buddhima Ruwanmini Gamlath Gamlath Ralalage

This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information. First, we consider two stochastic models called query-commit and price-of-information where the algo ...

EPFL2021

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Mikhail Kapralov, Slobodan Mitrovic, Jakab Tardos, Ashkan Norouzi Fard

Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...

ASSOC COMPUTING MACHINERY2020

A Crossing Lemma for Multigraphs

János Pach

Let G be a drawing of a graph with n vertices and e > 4n edges, in which no two adjacent edges cross and any pair of independent edges cross at most once. According to the celebrated Crossing Lemma of Ajtai, Chvatal, Newborn, Szemeredi and Leighton, the nu ...

SPRINGER2020

Symbolic Algorithms for Token Swapping

Giovanni De Micheli, Mathias Soeken, Bruno Schmitt Antunes

We study different symbolic algorithms to solve two related reconfiguration problems on graphs: the token swapping problem and the permutation routing via matchings problem. Input to both problems is a connected graph with labeled vertices and a token in e ...

2020

Thrackles: An improved upper bound

János Pach, Radoslav Fulek

A thrackle is a graph drawn in the plane so that every pair of its edges meet exactly once: either at a common end vertex or in a proper crossing. We prove that any thrackle of n vertices has at most 1.3984n edges. Quasi-thrackles are defined similarly, ex ...

ELSEVIER SCIENCE BV2019

Deforming Tessellations for the Segmentation of Cell Aggregates

Michaël Unser, Daniel Sage, Anaïs Laure Marie-Thérèse Badoual, Aymeric Alexandre Galan

We present a new active contour to segment cell aggregates. We describe it by a smooth tessellation that is attracted toward the cell membranes. Our approach relies on subdivision schemes that are tightly linked to the theory of wavelets. The shape is enco ...

IEEE2019

Approximating the rectilinear crossing number

János Pach

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 ...

2019

Ordered Graphs And Large Bi-Cliques In Intersection Graphs Of Curves

János Pach, Istvan Tomon

An ordered graph G(

COMENIUS UNIV2019