Publication

Optimal subtrees and extensions

Thomas Liebling
1982
Conference Papers

Abstract

We consider the problem of finding an optimal family of nested rooted subtrees of a tree. We give a linear algorithm for the associated 1.p. for this problem. A generalization of this problem is that of finding an optimal "lower closed set" of nodes in an acyclic graph for which polyhedral and polarity characterization are given. these problem are useful relaxations when solving more complicated sequencing problems.

Official source

Graph Chat

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.

Thomas Liebling
1982
Conference Papers

Abstract

Official source

Related concepts (32)

Directed acyclic graph

In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called arcs), with each edge directed from one vertex to another, such that following those directions will never form a closed loop. A directed graph is a DAG if and only if it can be topologically ordered, by arranging the vertices as a linear ordering that is consistent with all edge directions.

Hypergraph

In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, a directed hypergraph is a pair , where is a set of elements called nodes, vertices, points, or elements and is a set of pairs of subsets of . Each of these pairs is called an edge or hyperedge; the vertex subset is known as its tail or domain, and as its head or codomain. The order of a hypergraph is the number of vertices in .

Tree (graph theory)

In graph theory, a tree is an undirected graph in which any two vertices are connected by path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees. A polytree (or directed tree or oriented tree or singly connected network) is a directed acyclic graph (DAG) whose underlying undirected graph is a tree.

Related publications (32)

Optimal subtrees and extensions

Chat with Graph Search

Time-Space Trade-Offs for Sumcheck

Sensor network localization has a benign landscape after low-dimensional relaxation

System-Level Co-design and Co-optimization of Heterogeneous Platforms for Deep-Learning Workloads