Concept

Feedback arc set

Related publications (41)

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.

Majority-Inverter Graph for FPGA Synthesis

Giovanni De Micheli, Paolo Ienne, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù, David Novo Bruna, Ana Petkovska

In this paper, we present an FPGA synthesis flow based on Majority-Inverter Graph (MIG). An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. MIG manipulation is supported by a consistent alge ...

2015

Homometric sets in trees

Radoslav Fulek, Slobodan Mitrovic

Let G = (V, E) denote a simple graph with vertex set V and edge set E. The profile of a vertex set V' subset of V denotes the multiset of pairwise distances between the vertices of V'. Two disjoint subsets of V are homometric if their profiles are the same ...

Academic Press Ltd- Elsevier Science Ltd2014

Majority-Inverter Graph: A Novel Data-Structure and Algorithms for Efficient Logic Optimization

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

In this paper, we present Majority-Inverter Graph (MIG), a novel logic representation structure for efficient optimization of Boolean functions. An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented e ...

2014

On grids in topological graphs

János Pach

A topological graph G is a graph drawn in the plane with vertices represented by points and edges represented by continuous arcs connecting the vertices. If every edge is drawn as a straight-line segment, then G is called a geometric graph. A k-grid in a t ...

Elsevier Science Bv2014

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

Bartosz Maria Walczak, Michal Lason

A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line L if the intersection of any member with L is a nonempty segment. It is proved that the intersection graphs of simple families of com ...

Springer2014

Hardness of Vertex Deletion and Project Scheduling

Ola Nils Anders Svensson

Assuming the Unique Games Conjecture, we show strong inapproximability results for two natural vertex deletion problems on directed graphs: for any integer k ≥ 2 and arbitrary small ε > 0, the Feedback Vertex Set problem and the DAG Vertex Deletion problem ...

Springer2012

Graph Drawing

Radoslav Fulek, Fabrizio Frati

In this paper we study the page number of upward planar directed acyclic graphs. We prove that the page number of any upward planar directed acyclic graph G is a function of the page number of a four-connected subgraph of G; further, we provide an upper bo ...

Springer Berlin Heidelberg2012

Primal-dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs

Carsten Moldenhauer

NODE-WEIGHTED STEINER FOREST is the following problem: Given an undirected graph, a set of pairs of terminal vertices, a weight function on the vertices, find a minimum weight set of vertices that includes and connects each pair of terminals. We consider t ...

Academic Press Inc Elsevier Science2011

A scenario approach for estimating the suboptimality of linear decision rules in two-stage robust optimization

Daniel Kuhn

Robust dynamic optimization problems involving adaptive decisions are computationally intractable in general. Tractable upper bounding approximations can be obtained by requiring the adaptive decisions to be representable as linear decision rules (LDRs). I ...

IEEE2011

Approximating Graphic TSP by Matchings

Ola Nils Anders Svensson

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leadi ...

IEEE Computer Society2011