Rank-Deficient Quadratic-Form Maximization Over M-Phase Alphabet: Polynomial-Complexity Solvability And Algorithmic Developments
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.
Precoloring extension problems are known to be NP-complete in several classes of graphs. Here, we consider precolorings of cographs with not only stable sets but also with cliques. We give polynomial time algorithms to extend such a precoloring in an optim ...
Failure location in transparent optical networks is difficult because of the large amount of alarms that a failure can trigger and because of corrupted alarms. One problem that network operators often face is how to set the thresholds in monitoring devices ...
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 ...
We study the complexity and expressive power of conjunctive queries over unranked labeled trees represented using a variety of structure relations such as "child'', "descendant'', and "following'' as well as unary relations for node labels. We establish a ...
A temporal interface for a system component is a finite automaton that specifies the legal sequences of input events. We evaluate and compare three different algorithms for automatically extracting the temporal interface from the transition graph of a comp ...
In the population protocol model introduced by Angluin et al. [2], a collection of agents, which are modelled by finite state machines, move around unpredictably and have pairwise interactions. The ability of such systems to compute functions on a multiset ...
Functionalism serves as the guiding concept of this piece of work, on the example of which shall be traced the changes that took place in modern architecture between 1930 and 1950. This choice seems appropriate since Functionalism is a particularly relevan ...
Simultaneous link failures are common in IP networks \cite{Markopoulou04}. In this paper, we develop a technique for locating multiple failures in Service Provider or Enterprise IP networks using active measurement. We propose a two-phased approach that mi ...
We address the weighted max-cut problem, or equivalently the problem of maximizing a quadratic form in n binary variables. If the underlying (symmetric) matrix is positive semidefinite of fixed rank d, then the problem can be reduced to searching the extre ...
4-Nitrophenyl (NP) sulfones were successfully employed in the modified Julia olefination reaction with carbonyl compds. The olefination reaction proceeds through a sequence of aldol addn., Smiles rearrangement, and elimination. The sulfones are easily prep ...
