Publications related to Unambiguous DNFs and Alon-Saks-Seymour

Chebyshev polynomial approximation for transductive learning on graphs

The goal of transductive learning is to find a way to recover the labels of lots of data with only a few known samples. In this work, we will work on graphs for two reasons. First, it’s possible to construct a graph from a given dataset with features. The ...

2011

Scalable and Secure Aggregation in Distributed Networks

Rachid Guerraoui, Anne-Marie Kermarrec, Hamza Harkous, Florian Huc

We consider the problem of computing an aggregation function in a \emph{secure} and \emph{scalable} way. Whereas previous distributed solutions with similar security guarantees have a communication cost of

O(n^3)

, we present a distributed protocol that r ...

CoRR2011

Local Graph-based Distributed Control for Safe Highway Platooning

Alcherio Martinoli, Sven Adrian Gowal, Riccardo Falconi

Using graph theory, this paper investigates how a group of vehicles, endowed with local positioning capabilities (range and bearing to other vehicles), can keep a predefined formation. We propose a longitudinal and lateral controller that stabilizes a syst ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010

Graph based distributed control of non-holonomic vehicles endowed with local positioning information engaged in escorting missions

Alcherio Martinoli, Sven Adrian Gowal, Riccardo Falconi

Using graph theory, this paper investigates how a group of robots, endowed with local positioning (range and bearing from other robots), can be engaged in a leader- following mission whilst keeping a predefined configuration. The possibility to locally cha ...

IEEE2010

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

Paolo Ienne, Philip Brisk, Ajay Kumar Verma

An optimal linear-time algorithm for interprocedural register allocation in high level synthesis is presented. Historically, register allocation has been modeled as a graph coloring problem, which is nondeterministic polynomial time-complete in general; ho ...

2010

Coloring axis-parallel rectangles

János Pach, Gábor Tardos

For every k and r, we construct a finite family of axis-parallel rectangles in the plane such that no matter how we color them with k colors, there exists a point covered by precisely r members of the family, all of which have the same color. For r = 2, th ...

2010

On the power of combinatorial and spectral invariants

We extend the traditional spectral invariants (spectrum and angles) by a stronger polynomial time computable graph invariant based on the angles between projections of standard basis vectors into the eigenspaces (in addition to the usual angles between sta ...

2010

Graph-Based Distributed Control for Non-holonomic Vehicles Engaged in a Reconfiguration Task using Local Positioning Information

Alcherio Martinoli, Sven Adrian Gowal, Riccardo Falconi

Formation building and keeping among vehicles has been studied for many years, since 1987 with Reynold's rules. This paper presents a control algorithm, based on recent work in graph theory, able to reconfigure static formations of non-holonomic vehicles e ...

2009

Chasing the Weakest System Model for Implementing Omega and Consensus

Martin Hutle

Aguilera et al. and Malkhi et al. presented two system models, which are weaker than all previously proposed models where the eventual leader election oracle Omega can be implemented, and thus, consensus can also be solved. The former model assumes unicast ...

2009

Some coloring and walking problems in graphs

Benjamin Leroy-Beaulieu

Graph theory is an important topic in discrete mathematics. It is particularly interesting because it has a wide range of applications. Among the main problems in graph theory, we shall mention the following ones: graph coloring and the Hamiltonian circuit ...

EPFL2008

Unambiguous DNFs and Alon-Saks-Seymour

Graph Chatbot

Chat with Graph Search

Chebyshev polynomial approximation for transductive learning on graphs

Scalable and Secure Aggregation in Distributed Networks

Local Graph-based Distributed Control for Safe Highway Platooning

Graph based distributed control of non-holonomic vehicles endowed with local positioning information engaged in escorting missions

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

Coloring axis-parallel rectangles

On the power of combinatorial and spectral invariants

Graph-Based Distributed Control for Non-holonomic Vehicles Engaged in a Reconfiguration Task using Local Positioning Information

Chasing the Weakest System Model for Implementing Omega and Consensus

Some coloring and walking problems in graphs

Scalable and Secure Aggregation in Distributed Networks

Local Graph-based Distributed Control for Safe Highway Platooning

Chebyshev polynomial approximation for transductive learning on graphs

Some coloring and walking problems in graphs

On the power of combinatorial and spectral invariants

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

Graph based distributed control of non-holonomic vehicles endowed with local positioning information engaged in escorting missions

Chasing the Weakest System Model for Implementing Omega and Consensus

Coloring axis-parallel rectangles

Graph-Based Distributed Control for Non-holonomic Vehicles Engaged in a Reconfiguration Task using Local Positioning Information