Concept

Graphe cycle

Publications associées (85)

Majority-Inverter Graph: A Novel Data-Structure and Algorithms for Efficient Logic Optimization

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù

In this paper, we present Majority-Inverter Graph (MIG), a novel logic representation structure for efficient optimization of Boolean functions. An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented e ...

2014

On grids in topological graphs

János Pach

A topological graph G is a graph drawn in the plane with vertices represented by points and edges represented by continuous arcs connecting the vertices. If every edge is drawn as a straight-line segment, then G is called a geometric graph. A k-grid in a t ...

Elsevier Science Bv2014

Tangles and Degenerate Tangles

Andres Jacinto Ruiz Vargas

We study some variants of Conway’s thrackle conjecture. A tangle is a graph drawn in the plane such that its edges are represented by continuous arcs, and any two edges share precisely one point, which is either a common endpoint or an interior point at wh ...

Springer Berlin Heidelberg2013

Active topology inference using network coding

Christina Fragouli

Our goal, in this paper, is to infer the topology of a network when (i) we can send probes between sources and receivers at the edge of the network and (ii) intermediate nodes can perform simple network coding operations, i.e., additions. Our key intuition ...

2013

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

Aleksander Madry

We present an O(m^10/7) = O(m^1.43)-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min{m^1/2, n^2/3}) runni ...

IEEE2013

Overview of New Approaches for Approximating TSP

Ola Nils Anders Svensson

n this extended abstract, we survey some of the recent results on approximating the traveling salesman problem on graphic metrics. We start by briefly explaining the algorithm of Oveis Gharan et al. [1] that has strong similarities to Christofides’ famo ...

Springer2013

THE NUMBER OF EDGES IN k-QUASI-PLANAR GRAPHS

János Pach

A graph drawn in the plane is called k-quasi-planar if it does not contain k pair-wise crossing edges. It has been conjectured for a long time that for every fixed k, the maximum number of edges of a k-quasi-planar graph with n vertices is O(n). The best k ...

Siam Publications2013

On the Sparsity of Wavelet Coefficients for Signals on Graphs

Pierre Vandergheynst, Benjamin Ricaud, David Shuman

A number of new localized, multiscale transforms have recently been introduced to analyze data residing on weighted graphs. In signal processing tasks such as regularization and compression, much of the power of classical wavelets on the real line is deriv ...

Spie-Int Soc Optical Engineering2013

Simulation of Urban Energy Flow: A Graph Theory Inspired Approach

Jean-Louis Scartezzini, Jérôme Henri Kämpf, Diane Perez

Following the increased consciousness regarding global warming and other environmental issues, there is a growing urge in cities for a more rational energy supply and use in buildings. In parallel, the range of possible actions has broaden, from building r ...

EPFL Solar Energy and Building Physics Laboratory (LESO-PB)2013

Markov Decision Process Based Energy-Efficient On-Line Scheduling for Slice Parallel Video Decoders on Multicore Systems

Pascal Frossard, David Atienza Alonso, Karim Kanoun

We consider the problem of energy-efficient on-line scheduling for slice-parallel video decoders on multicore systems. We assume that each of the processors are Dynamic Voltage Frequency Scaling (DVFS) enabled such that they can independently trade off per ...

Ieee-Inst Electrical Electronics Engineers Inc2013

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search