Concept
Subgraph isomorphism problem
Related publications (44)
Pliable Index Coding
Christina Fragouli, Siddhartha Brahma
We propose a new formulation of the index coding problem, where instead of demanding a specific message, clients are “pliable” and are happy to receive any one message they do not have. We prove that with this relaxation, although some instances of this pr ...
Ieee2012On the Brauer group of diagonal quartic surfaces
We obtain an easy sufficient condition for the Brauer group of a diagonal quartic surface D over Q to be algebraic. We also give an upper bound for the order of the quotient of the Brauer group of D by the image of the Brauer group of Q. The proof is based ...
2011MARGIN: 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 ...
2010Connected facility location via random facility sampling and core detouring
Friedrich Eisenbrand, Thomas Rothvoss
We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the ...
2010Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks
This article concerns the following question arising in computational evolutionary biology. For a given subclass of phylogenetic networks, what is the maximum value of 0
2010EDF-schedulability of synchronous periodic task systems is coNP-hard
Friedrich Eisenbrand, Thomas Rothvoss
In the synchronous periodic task model, a set \tau_1,...,\tau_n of tasks is given, each releasing jobs of running time c_i with relative deadline d_i, at each integer multiple of the period p_i. It is a classical result that Earliest Deadline First (EDF) i ...
2010Isomorphism Problems of Noncommutative Deformations of Type D Kleinian Singularities
We construct all possible noncommutative deformations of a Kleinian singularity C-2/Gamma of type D-n in terms of generators and relations, and solve the isomorphism problem for the associative algebras thus constructed. We prove that (in our parametrizati ...
2009Delay with network coding and feedback
Christina Fragouli, Lorenzo Keller
We consider the problem of minimizing delay when broadcasting over erasure channels with feedback. A sender wishes to communicate the same set of mu messages to several receivers over separate erasure channels. The sender can broadcast a single message or ...
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2009How to play the “Names Game”: Patent retrieval comparing different heuristics
Stéphane Lhuillery, Julio Diego Salvador Raffo
Patent statistics represent a critical tool for scholars, statisticians and policy makers interested in innovation and intellectual property rights. Many analyses are based on heterogeneous methods delineating the inventors’ or firms’ patent portfolios wit ...
Elsevier2009How to play 'the Names Game': Patent retrieval comparing different heuristics
Stéphane Lhuillery, Julio Diego Salvador Raffo
Patent statistics represent a critical tool for scholars, statisticians and policy makers interested in innovation and intellectual property rights. Many analyses are based on heterogeneous methods delineating the inventors' or firms' patent portfolios wit ...
2009