Publications related to New Graph Algorithms via Polyhedral Techniques

Embedded deformation for shape manipulation

We present an algorithm that generates natural and intuitive deformations via direct manipulation for a wide range of shape representations and editing scenarios. Our method builds a space deformation represented by a collection of affine transformations o ...

2007

An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

We consider the metric uncapacitated facility location problem(UFL). In this paper we modify the (1 + 2/e)-approximation algorithm of Chudak and Shmoys to obtain a new (1.6774,1.3738)- approximation algorithm for the UFL problem. Our linear programing roun ...

Springer2007

Optimal polynomial-time interprocedural register allocation for high-level synthesis and ASIP design

Paolo Ienne, Philip Brisk, Ajay Kumar Verma

Register allocation, in high-level synthesis and ASIP design, is the process of determining the number of registers to include in the resulting circuit or processor. The goal is to allocate the minimum number of registers such that no scalar variable is sp ...

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

Stability and Delay Bounds in Heterogeneous Networks of Aggregate Schedulers

Jean-Yves Le Boudec, Gianluca Rizzo

Aggregate scheduling is one of the most promising solutions to the issue of scalability in networks, like DiffServ networks and high speed switches, where hard QoS guarantees are required. For networks of FIFO aggregate schedulers, the main existing suffic ...

2007

An approach to modelling and verification of component based systems

Joseph Sifakis

We build on a framework for modelling and investigating component-based systems that strictly separates the description of behavior of components from the way they interact. We discuss various properties of system behavior as liveness, local progress, loca ...

2007

TCHo: a Hardware-Oriented Trapdoor Cipher

Serge Vaudenay, Willi Meier, Jean-Philippe Aumasson

This paper improves the Finiasz-Vaudenay construction of TCHo, a hardware-oriented public-key cryptosystem, whose security relies in the hardness of finding a low-weight multiple of a given polynomial, and on the decoding of certain noisy cyclic linear cod ...

Springer2007

Motion Detection Circuits for a Time-To-Travel Algorithm

The paper describes a new motion detection circuit that extracts motion information based on a time-to-travel algorithm. The front-end photoreceptor adapts over 7 decades of background intensity and motion information can be extracted down to a contrast va ...

IEEE2007

Gossiping in a Multi-Channel Radio Network (An Oblivious Approach to Coping With Malicious Interference)

Rachid Guerraoui, Seth Gilbert

We study oblivious deterministic gossip algorithms for multi-channel radio networks with a malicious adversary. In a multi-channel network, each of the n processes in the system must choose, in each round, one of the c channels of the system on which to pa ...

Springer2007

Average case analysis of multichannel sparse approximations using p- thresholding

Pierre Vandergheynst, Rémi Gribonval, Karin Schnass

This paper introduces

p

-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries. We work out both worst case and average case recovery analyses of this algorithm and show that the latte ...

2007

Average case analysis of multichannel sparse approximations using p-thresholding - art. no. 67011X

Pierre Vandergheynst, Rémi Gribonval, Karin Schnass

This paper introduces p-thresholding, an algorithm to compute simultaneous sparse approximations of multichannel signals over redundant dictionaries. We work out both worst case and average case recovery analyses of this algorithm and show that the latter ...

Spie-Int Soc Optical Engineering, Po Box 10, Bellingham, Wa 98227-0010 Usa2007

New Graph Algorithms via Polyhedral Techniques

Graph Chatbot

Chat with Graph Search

Embedded deformation for shape manipulation

An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

Optimal polynomial-time interprocedural register allocation for high-level synthesis and ASIP design

Stability and Delay Bounds in Heterogeneous Networks of Aggregate Schedulers

An approach to modelling and verification of component based systems

TCHo: a Hardware-Oriented Trapdoor Cipher

Motion Detection Circuits for a Time-To-Travel Algorithm

Gossiping in a Multi-Channel Radio Network (An Oblivious Approach to Coping With Malicious Interference)

Average case analysis of multichannel sparse approximations using p- thresholding

Average case analysis of multichannel sparse approximations using p-thresholding - art. no. 67011X

Optimal polynomial-time interprocedural register allocation for high-level synthesis and ASIP design

An approach to modelling and verification of component based systems

Stability and Delay Bounds in Heterogeneous Networks of Aggregate Schedulers

Motion Detection Circuits for a Time-To-Travel Algorithm

An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

TCHo: a Hardware-Oriented Trapdoor Cipher

Embedded deformation for shape manipulation

Gossiping in a Multi-Channel Radio Network (An Oblivious Approach to Coping With Malicious Interference)

Average case analysis of multichannel sparse approximations using p- thresholding

Average case analysis of multichannel sparse approximations using p-thresholding - art. no. 67011X