Publication

On the complexity of fixed parameter clique and dominating set

Related publications (108)

Graph Chatbot

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.

Mutual information measures for subclass error-correcting output codes classification

Nikolaos Arvanitopoulos Darginis

Error-Correcting Output Codes (ECOCs) reveal a common way to model multi-class classification problems. According to this state of the art technique, a multi-class problem is decomposed into several binary ones. Additionally, on the ECOC framework we can a ...

2010

Sorting signed permutations by inversions in O(nlogn) time

Bernard Moret, Yu Lin, Vaibhav Rajan, Krister Swenson

The study of genomic inversions (or reversals) has been a mainstay of computational genomics for nearly 20 years. After the initial breakthrough of Hannenhalli and Pevzner, who gave the first polynomial-time algorithm for sorting signed permutations by inv ...

2010

On the benefits of vector network coding

Christina Fragouli, Javad Ebrahimi Boroojeni

In vector network coding, the source multi- casts information by transmitting vectors of length L, while intermediate nodes process and combine their incoming packets by multiplying them with L × L coding matrices that play a similar role as coding coeffic ...

2010

Refined quorum systems

Rachid Guerraoui, Marko Vukolic

It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contenti ...

2010

MARGIN: Maximal frequent subgraph mining

Ramachandra Satyanarayana Valluri

The exponential number of possible subgraphs makes the problem of frequent subgraph mining a challenge. The set of maximal frequent subgraphs is much smaller to that of the set of frequent subgraphs providing ample scope for pruning. MARGIN is a maximal su ...

2010

Algorithm/Architecture Co-Exploration of Visual Computing: Overview and Future Perspectives

Marco Mattavelli

Concurrently exploring both algorithmic and architectural optimizations is a new design paradigm. This survey paper addresses the latest research and future perspectives on the simultaneous development of video coding, processing, and computing algorithms ...

2009

EPnP: An Accurate O(n) Solution to the PnP Problem

Pascal Fua, Vincent Lepetit

We propose a non-iterative solution to the PnP problem-the estimation of the pose of a calibrated camera from n 3D-to-2D point correspondences-whose computational complexity grows linearly with n. This is in contrast to state-of-the-art methods that are O( ...

Springer Verlag2009

Sorting signed permutations by inversions in O(nlogn) time

Bernard Moret, Yu Lin, Vaibhav Rajan, Krister Swenson

Springer2009

Reducing Memory Requirements for Combinatorial Attacks on NTRU via Multiple Birthdays

In this paper we view the possibilities to lance a multiple (iterative) birthday attack on NTRU. Recently Wagner's algorithm for the generalized birthday problem [9] allowed to speed-up several combinatorial attacks. However, in the case of NTRU we can not ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2009

Abstractions for asynchronous distributed computing with malicious players

Marko Vukolic

In modern distributed systems, failures are the norm rather than the exception. In many cases, these failures are not benign. Settings such as the Internet might incur malicious (also called Byzantine or arbitrary) behavior and asynchrony. As a result, and ...

EPFL2008