Publications related to Dominating set

Maximum Independent Set: Self-Training through Dynamic Programming

Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly construc ...

2023

Safe Zeroth-Order Convex Optimization Using Quadratic Local Approximations

Giancarlo Ferrari Trecate, Maryam Kamgarpour, Yuning Jiang, Baiwei Guo

We address black-box convex optimization problems, where the objective and constraint functions are not explicitly known but can be sampled within the feasible set. The challenge is thus to generate a sequence of feasible points converging towards an optim ...

2023

Unambiguous DNFs and Alon-Saks-Seymour

Mika Tapani Göös, Siddhartha Jain

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...

IEEE COMPUTER SOC2022

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

Ola Nils Anders Svensson, Moran Feldman, Rico Zenklusen, Ashkan Norouzi Fard

We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multi-player model t ...

ASSOC COMPUTING MACHINERY2020

Manycore clique enumeration with fast set intersections

Paolo Ienne, Kubilay Atasu, Radu Ioan Stoica, Jovan Blanusa

Listing all maximal cliques of a given graph has important applications in the analysis of social and biological networks. Parallelisation of maximal clique enumeration (MCE) algorithms on modern manycore processors is challenging due to the task-level par ...

ACM2020

New approach for time-resolved and dynamic investigations on nanoparticles agglomeration

Francesco Stellacci, Antonia Neels, Alex Dommann, Urszula Beata Cendrowska, Claudio Toncelli

Nanoparticle (NP) colloidal stability plays a crucial role in biomedical application not only for human and environmental safety but also for NP efficiency and functionality. NP agglomeration is considered as a possible process in monodispersed NP colloida ...

TSINGHUA UNIV PRESS2020

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

Ola Nils Anders Svensson, Abbas Bazzi

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

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.

Dominating set

Maximum Independent Set: Self-Training through Dynamic Programming

Safe Zeroth-Order Convex Optimization Using Quadratic Local Approximations

Unambiguous DNFs and Alon-Saks-Seymour

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

Manycore clique enumeration with fast set intersections

New approach for time-resolved and dynamic investigations on nanoparticles agglomeration

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

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

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

Graph Chatbot

Chat with Graph Search

Manycore clique enumeration with fast set intersections

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

Maximum Independent Set: Self-Training through Dynamic Programming

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Unambiguous DNFs and Alon-Saks-Seymour

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

New approach for time-resolved and dynamic investigations on nanoparticles agglomeration

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

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