Greedy coloring

Formal sciences
Mathematics
Discrete mathematics
Graph theory

About
Privacy
Disclaimer

Graph Chatbot

Related publications (25)

Page 2 of 2

Localizing Polygonal Objects in Man-Made Environments

Xiaolu Sun

Object detection is a significant challenge in Computer Vision and has received a lot of attention in the field. One such challenge addressed in this thesis is the detection of polygonal objects, which are prevalent in man-made environments. Shape analysis ...

EPFL2015

The Erdos-Hajnal conjecture for rainbow triangles

János Pach

We prove that every 3-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order ohm(n(1/3) log(2) n) which uses at most two colors, and this bound is tight up to a constant factor. This verifies a conjectu ...

Academic Press Inc Elsevier Science2015

Downsampling of Signals on Graphs Via Maximum Spanning Trees

Quy Ha Nguyen, Minh Do

Downsampling of signals living on a general weighted graph is not as trivial as of regular signals where we can simply keep every other samples. In this paper we propose a simple, yet effective downsampling scheme in which the underlying graph is approxima ...

Ieee-Inst Electrical Electronics Engineers Inc2015

Improving Christofides' Algorithm for the s-t Path TSP

We present a deterministic (1+root 5/2)-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the t ...

Assoc Computing Machinery2015

Efficient greedy algorithms for high-dimensional parameter spaces with applications to empirical interpolation and reduced basis methods

Jan Sickmann Hesthaven, Benjamin Stamm

We propose two new and enhanced algorithms for greedy sampling of high- dimensional functions. While the techniques have a substantial degree of generality, we frame the discussion in the context of methods for empirical interpolation and the devel- opment ...

EDP Sciences2014