Concept

Théorème de Kőnig (théorie des graphes)

Publications associées (30)

No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...

INFORMS2019

The Sketching Complexity of Graph and Hypergraph Counting

Mikhail Kapralov, John Michael Goddard Kallaugher

Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been ...

IEEE COMPUTER SOC2018

Finding Perfect Matchings in Bipartite Hypergraphs

Chidambaram Annamalai

Haxell's condition [14] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perf ...

SPRINGER HEIDELBERG2018

Matching fields and lattice points of simplices

Georg Peter Loho

We show that the Chow covectors of a linkage matching field define a bijection of lattice points and we demonstrate how one can recover the linkage matching field from this bijection. This resolves two open questions from Sturmfels & Zelevinsky (1993) on l ...

2020

Nanoparticle Conjugation of Human Papillomavirus 16 E7-long Peptides Enhances Therapeutic Vaccine Efficacy against Solid Tumors in Mice

Douglas Hanahan, Mélanie Louise Tichet, Melody Swartz, Stephan Wullschleger, Gabriele Galliverti, Sylvie Hauert

Treatment of patients bearing human papillomavirus (HPV)-related cancers with synthetic long-peptide (SLP) therapeutic vaccines has shown promising results in clinical trials against premalignant lesions, whereas responses against later stage carcinomas ha ...

AMER ASSOC CANCER RESEARCH2018

When Stuck, Flip a Coin : New Algorithms for Large-Scale Tasks

Slobodan Mitrovic

Many modern services need to routinely perform tasks on a large scale. This prompts us to consider the following question: How can we design efficient algorithms for large-scale computation? In this thesis, we focus on devising a general strategy to addr ...

EPFL2018

Geometric Graph Matching Using Monte Carlo Tree Search

Pascal Fua, Jan Kybic, Miguel Amável Dos Santos Pinheiro

We present an efficient matching method for generalized geometric graphs. Such graphs consist of vertices in space connected by curves and can represent many real world structures such as road networks in remote sensing, or vessel networks in medical imagi ...

Ieee Computer Soc2017

Extension complexity of stable set polytopes of bipartite graphs

Yuri Faenza, Manuel Francesco Aprile

The extension complexity xc(P) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let STAB(G) be the convex hull of the stable sets of G. ...

Springer2017

A semi-algebraic version of Zarankiewicz's problem

János Pach

A bipartite graph G is semi-algebraic in R-d if its vertices are represented by point sets P,Q subset of R-d and its edges are defined as pairs of points (p,q) epsilon P x Q that satisfy a Boolean combination of a fixed number of polynomial equations and i ...

European Mathematical Soc2017

Decomposition of Multiple Packings with Subquadratic Union Complexity

János Pach, Bartosz Maria Walczak

Suppose k is a positive integer and X is a k-fold packing of the plane by infinitely many arc-connected compact sets, which means that every point of the plane belongs to at most k sets. Suppose there is a function f(n) = o(n(2)) with the property that any ...

Cambridge Univ Press2016