Publications related to Optimal subtrees and extensions

Exact Synthesis of LTL Properties from Traces

We present an exact approach to synthesize temporal-logic formulas in linear temporal logic (LTL) from a set of given positive and negative example traces. Our approach uses topology structures, in particular partial DAGs, to partition the search space int ...

IEEE2019

LUT Mapping and Optimization for Majority-Inverter Graphs

Giovanni De Micheli, Mathias Soeken, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù, Winston Jason Haaswijk

A Majority-Inverter Graph (MIG) is a directed acyclic graph in which every vertex represents a three-input majority operation and edges may be complemented to indicate operand inversion. MIGs have algebraic and Boolean properties that enable efficie ...

2016

AiiDA: automated interactive infrastructure and database for computational science

Nicola Marzari, Giovanni Pizzi, Boris Kozinsky, Andrea Cepellotti, Riccardo Sabatini

Computational science has seen in the last decades a spectacular rise in the scope, breadth, and depth of its efforts. Notwithstanding this prevalence and impact, it is often still performed using the renaissance model of individual artisans gathered in a ...

Elsevier Science Bv2016

Boolean logic optimization in majority-inverter graphs

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

We present a Boolean logic optimization framework based on Majority-Inverter Graph (MIG). An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. Current MIG optimization is supported by a consistent alge ...

2016

Boolean Logic Optimization in Majority-Inverter Graphs

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

We present a Boolean logic optimization framework based on Majority-Inverter Graph (MIG). An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. Current MIG optimization is supported by a consiste ...

2015

Cellular properties of nilpotent spaces

Jérôme Scherer

We show that cellular approximations of nilpotent Postnikov stages are always nilpotent Postnikov stages, in particular classifying spaces of nilpotent groups are turned into classifying spaces of nilpotent groups. We use a modified Bousfield-Kan homology ...

Geometry & Topology Publications2015

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

Steiner Tree Approximation via Iterative Randomized Rounding

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem w ...

Assoc Computing Machinery2013

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

Reduced-Dimension Linear Transform Coding of Correlated Signals in Networks

Michael Christoph Gastpar, Naveen Goela

A model called the linear transform network (LTN) is proposed to analyze the compression and estimation of correlated signals transmitted over directed acyclic graphs (DAGs). An LTN is a DAG network with multiple source and receiver nodes. Source nodes tra ...

Institute of Electrical and Electronics Engineers2012

Optimal subtrees and extensions

Graph Chatbot

Chat with Graph Search

Exact Synthesis of LTL Properties from Traces

LUT Mapping and Optimization for Majority-Inverter Graphs

AiiDA: automated interactive infrastructure and database for computational science

Boolean logic optimization in majority-inverter graphs

Boolean Logic Optimization in Majority-Inverter Graphs

Cellular properties of nilpotent spaces

Node-weighted network design and maximum sub-determinants

Steiner Tree Approximation via Iterative Randomized Rounding

Active topology inference using network coding

Reduced-Dimension Linear Transform Coding of Correlated Signals in Networks

Boolean logic optimization in majority-inverter graphs

Boolean Logic Optimization in Majority-Inverter Graphs

Exact Synthesis of LTL Properties from Traces

LUT Mapping and Optimization for Majority-Inverter Graphs

Active topology inference using network coding

Node-weighted network design and maximum sub-determinants

Reduced-Dimension Linear Transform Coding of Correlated Signals in Networks

Steiner Tree Approximation via Iterative Randomized Rounding

AiiDA: automated interactive infrastructure and database for computational science

Cellular properties of nilpotent spaces