Publications related to Edge cover

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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

Asyrnptotics for the Turan number of Berge-K-2,K-t

Abhishek Methuku

Let F be a graph. A hypergraph is called Berge-F if it can be obtained by replacing each edge in F by a hyperedge containing it. Let F be a family of graphs. The Turan number of the family Berge-F is the maximum possible number of edges in an r-uniform hyp ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

On the Rainbow Turan number of paths

Abhishek Methuku

Let F be a fixed graph. The rainbow Turan number of F is defined as the maximum number of edges in a graph on n vertices that has a proper edge-coloring with no rainbow copy of F (i.e., a copy of F all of whose edges have different colours). The systematic ...

ELECTRONIC JOURNAL OF COMBINATORICS2019

Adaptive Majority Problems For Restricted Query Graphs And For Weighted Sets

Abhishek Methuku, Balázs Keszegh

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

COMENIUS UNIV2019

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Slobodan Mitrovic, Mohsen Ghaffari

We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum ve ...

ASSOC COMPUTING MACHINERY2018

Ramsey-Turan numbers for semi-algebraic graphs

János Pach

A semi-algebraic graph G = (V, E) is a graph where the vertices are points in R-d, and the edge set E is defined by a semi-algebraic relation of constant complexity on V. In this note, we establish the following Ramsey-Turan theorem: for every integer p >= ...

ELECTRONIC JOURNAL OF COMBINATORICS2018

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

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

Scaffold requirements for periodontal regeneration with enamel matrix derivative proteins

John Christopher Plummer, Laurent Mirko Dejace, Matteo Gregorio Modesto Marascio, Peter Fischer, Alessandra Apicella

Periodontitis affects the attachment of natural teeth, and infection or inflammation associated with periodontitis may affect peri-implant tissues. Enamel matrix derivative (EMD) proteins provide stimulation for self-regeneration of the damaged tissue when ...

Elsevier Science Bv2017

Edge cover

Graph Chatbot

Chat with Graph Search

Thrackles: An improved upper bound

Asyrnptotics for the Turan number of Berge-K-2,K-t

On the Rainbow Turan number of paths

Adaptive Majority Problems For Restricted Query Graphs And For Weighted Sets

The covering radius and a discrete surface area for non-hollow simplices

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Ramsey-Turan numbers for semi-algebraic graphs

The Sketching Complexity of Graph and Hypergraph Counting

Extension complexity of stable set polytopes of bipartite graphs

Scaffold requirements for periodontal regeneration with enamel matrix derivative proteins

The covering radius and a discrete surface area for non-hollow simplices

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

On the Rainbow Turan number of paths

Scaffold requirements for periodontal regeneration with enamel matrix derivative proteins

Extension complexity of stable set polytopes of bipartite graphs

Thrackles: An improved upper bound

Adaptive Majority Problems For Restricted Query Graphs And For Weighted Sets

Ramsey-Turan numbers for semi-algebraic graphs

Asyrnptotics for the Turan number of Berge-K-2,K-t

The Sketching Complexity of Graph and Hypergraph Counting