Publications related to Greedy coloring

Actuator Placement for Optimizing Network Performance under Controllability Constraints

Maryam Kamgarpour, Tyler Summers, Baiwei Guo, Orcun Karaca

With the rising importance of large-scale network control, the problem of actuator placement has received increasing attention. Our goal in this paper is to find a set of actuators minimizing the metric that measures the average energy consumption of the c ...

IEEE2019

Tight Bounds for Online Edge Coloring

David Wajc

Vizing's celebrated theorem asserts that any graph of maximum degree Delta admits an edge coloring using at most Delta + 1 colors. In contrast, Bar-Noy, Motwani and Naor showed over a quarter century ago that the trivial greedy algorithm, which uses 2 Delt ...

IEEE COMPUTER SOC2019

Distributed Coloring of Graphs with an Optimal Number of Colors

Etienne Michel François Bamas

This paper studies sufficient conditions to obtain efficient distributed algorithms coloring graphs optimally (i.e. with the minimum number of colors) in the LOCAL model of computation. Most of the work on distributed vertex coloring so far has focused on ...

SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS2019

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

Online Matching with General Arrivals

Ola Nils Anders Svensson, Mikhail Kapralov, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Andreas Maggiori, David Wajc

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomi ...

IEEE COMPUTER SOC2019

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

Reduced Numerical Approximation of Reduced Fluid-Structure Interaction Problems With Applications in Hemodynamics

Simone Deparis, Claudia Maria Colciago

This paper deals with fast simulations of the hemodynamics in large arteries by considering a reduced model of the associated fluid-structure interaction problem, which in turn allows an additional reduction in terms of the numerical discretisation. The re ...

2018

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic, Slobodan Mitrovic

We study the problem of maximizing a monotone submodular function subject to a cardinality constraint

k

, with the added twist that a number of items

\tau

from the returned set may be removed. We focus on the worst-case setting considered in Orlin et al ...

2017

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Justin Dean Ward

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a monotone increasing submodular function or ...

INFORMS2017

Greedy coloring

Graph Chatbot

Chat with Graph Search

Actuator Placement for Optimizing Network Performance under Controllability Constraints

Tight Bounds for Online Edge Coloring

Distributed Coloring of Graphs with an Optimal Number of Colors

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

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

Online Matching with General Arrivals

The Sketching Complexity of Graph and Hypergraph Counting

Reduced Numerical Approximation of Reduced Fluid-Structure Interaction Problems With Applications in Hemodynamics

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Actuator Placement for Optimizing Network Performance under Controllability Constraints

The Sketching Complexity of Graph and Hypergraph Counting

Online Matching with General Arrivals

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Tight Bounds for Online Edge Coloring

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

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Distributed Coloring of Graphs with an Optimal Number of Colors

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

Reduced Numerical Approximation of Reduced Fluid-Structure Interaction Problems With Applications in Hemodynamics