Concept

Sommet (géométrie)

Publications associées (23)

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

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

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

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, Aymeric Alexandre Galan, Anaïs Laure Marie-Thérèse Badoual

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

Ordered graphs and large bi-cliques in intersection graphs of curves

János Pach, Istvan Tomon

An ordered graph G(

ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019

New Moduli For Banach Spaces

Grigory Ivanov

Modifying the moduli of supporting convexity and supporting smoothness, we introduce new moduli for Banach spaces which occur, for example, as lengths of catheti of right-angled triangles (defined via so-called quasiorthogonality). These triangles have two ...

Tusi Mathematical Research Group2017

On Simplices in Diameter Graphs in R-4

Andrei Kupavskii

A graph G is a diameter graph in R-d if its vertex set is a finite subset in R-d of diameter 1 and edges join pairs of vertices a unit distance apart. It is shown that if a diameter graph G in R-4 contains the complete subgraph K on five vertices, then any ...

Maik Nauka/Interperiodica/Springer2017

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

Upper bounds for the perimeter of plane convex bodies

Filip Moric

We show that the maximum total perimeter of k plane convex bodies with disjoint interiors lying inside a given convex body C is equal to , in the case when C is a square or an arbitrary triangle. A weaker bound is obtained for general plane convex bodies. ...

Springer2014

Bowl Inversion of Surface-Adsorbed Sumanene

Bowl-shaped pi-conjugated compounds offer the possibility to study curvature-dependent host-guest interactions and chemical reactivity in ideal model systems. For surface-adsorbed pi bowls, however, only conformations with the bowl opening pointing away fr ...

Amer Chemical Soc2014

The number of distinct distances from a vertex of a convex polygon

János Pach, Rom Pinchasi, Gabriel Nivasch

Erd\H{o}s conjectured in 1946 that every n-point set P in convex position in the plane contains a point that determines at least floor(n/2) distinct distances to the other points of P. The best known lower bound due to Dumitrescu (2006) is 13n/36 - O(1). I ...

2013

Application of vertex and mass constraints in track-based alignment

Olivier Schneider, Maurizio Martinelli, Frédéric Guillaume Dupertuis, Christophe Salzmann, Vincent Fave

The software alignment of planar tracking detectors using samples of charged particle trajectories may lead to global detector distortions that affect vertex and momentum resolution. We present an alignment procedure that constrains such distortions by mak ...

Elsevier Science Bv2013

The Range of a Random Walk on a Comb

János Pach

The graph obtained from the integer grid Z x Z by the removal of all horizontal edges that do not belong to the x-axis is called a comb. In a random walk on a graph, whenever a walker is at a vertex v, in the next step it will visit one of the neighbors of ...

Electronic Journal Of Combinatorics2013

k-Quasi-Planar Graphs

A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. A topological graph is simple if every pair of its edges intersect at most once (either at a vertex or at their intersection). In 1996, Pach, Shahrokhi. and Szegedy [16 ...

Springer-Verlag Berlin2012

Finite Element Method on Riemann Surfaces and Applications to the Laplacian Spectrum

Marc Maintrot

The objective of this PhD thesis is the approximate computation of the solutions of the Spectral Problem associated with the Laplace operator on a compact Riemann surface without boundaries. A Riemann surface can be seen as a gluing of portions of the Hype ...

EPFL2012

Publications associées (23)

COMENIUS UNIV2019

Ordered graphs and large bi-cliques in intersection graphs of curves

János Pach, Istvan Tomon

An ordered graph G(

ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019