Publication

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al.

Publications associées (290)

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

Partitioning cographs into cliques and stable sets

Dominique de Werra, Tinaz Ekim

We consider the problem of partitioning the node set of a graph into p cliques and k stable sets, namely the (p,k)-coloring problem. Results have been obtained for general graphs \cite{hellcomp}, chordal graphs \cite{hellchordal} and cacti for the case whe ...

2005

Suboptimal colorings and solution of large chromatic scheduling problems

Ivo Blöchliger

Graph Coloring is a very active field of research in graph theory as well as in the domain of the design of efficient heuristics to solve problems which, due to their computational complexity, cannot be solved exactly (no guarantee that an optimal solution ...

EPFL2005

Mining Co-Change Clusters from Version Repositories

Dirk Thilo Beyer

Clusters of software artifacts that are frequently changed together are subsystem candidates, because one of the main goals of software design is to make changes local. The contribution of this paper is a visualization-based method that supports the identi ...

2005

A Propagation/Local Search Hybrid for Distributed Optimization

Boi Faltings, Adrian Petcu

We present a new hybrid algorithm for local search in distributed combinatorial optimization. This method is a mix between classical local search methods in which nodes take decisions based only on local information, and full inference methods that guarant ...

2005

A Multi-Criteria Message Forwarding Architecture for Wireless Sensor Networks

Ioannis Alagiannis, Manoussos Gavriil Athanassoulis

Wireless Sensor Networks (WSN) comprise a fast-developing research area with a vast spectrum of applications. A WSN design is influenced by many factors such as transmission errors, network topology and power consumption. Consequently, developing a WSN app ...

2005

Some combinatorial optimization problems in graphs with applications in telecommunications and tomography

David Schindl

The common point between the different chapters of the present work is graph theory. We investigate some well known graph theory problems, and some which arise from more specific applications. In the first chapter, we deal with the maximum stable set probl ...

EPFL2004

An algorithm for source location in directed graphs

Johanna Kristin Maria Becker

A polynomial time solution algorithm is described to find a smallest subset R of nodes of a directed graph D=(V,A) such that, for every node v in V-R, there are k edge-disjoint paths from R to v and there are l edge-disjoint paths from v to R. ...

2004

On Average Throughput Benefits for Network Coding

Christina Fragouli, Emina Soljanin

We calculate the average throughput benefit that network coding can offer as compared to routing for different classes of multicast configurations over directed graphs. The averaging is over the throughput each individual receiver experiences. For the case ...

2004

Trust Evaluation in Ad-Hoc Networks

Georgios Theodorakopoulos

An important concept in network security is trust, interpreted as a relation among entities that participate in various protocols. Trust relations are based on evidence related to the previous interactions of entities within a protocol. In this work, we ar ...

ACM Press2004

Network coding as a coloring problem (Invited paper)

Mohammad Amin Shokrollahi, Christina Fragouli, Emina Soljanin

We consider a multicast configuration with two sources, and translate the network code design problem to vertex coloring of an appropriately defined graph. This observation enables to derive code design algorithms and alphabet size bounds, as well as estab ...

2004