Multitree | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

In combinatorics and order theory, a multitree may describe either of two equivalent structures: a directed acyclic graph (DAG) in which there is at most one directed path between any two vertices, or equivalently in which the subgraph reachable from any vertex induces an undirected tree, or a partially ordered set (poset) that does not have four items a, b, c, and d forming a diamond suborder with a ≤ b ≤ d and a ≤ c ≤ d but with b and c incomparable to each other (also called a diamond-free poset). In computational complexity theory, multitrees have also been called strongly unambiguous graphs or mangroves; they can be used to model nondeterministic algorithms in which there is at most one computational path connecting any two states. Multitrees may be used to represent multiple overlapping taxonomies over the same ground set. If a family tree may contain multiple marriages from one family to another, but does not contain marriages between any two blood relatives, then it forms a multitree. In a directed acyclic graph, if there is at most one directed path between any two vertices, or equivalently if the subgraph reachable from any vertex induces an undirected tree, then its reachability relation is a diamond-free partial order. Conversely, in a diamond-free partial order, the transitive reduction identifies a directed acyclic graph in which the subgraph reachable from any vertex induces an undirected tree. A diamond-free family of sets is a family F of sets whose inclusion ordering forms a diamond-free poset. If D(n) denotes the largest possible diamond-free family of subsets of an n-element set, then it is known that and it is conjectured that the limit is 2. A polytree, a directed acyclic graph formed by orienting the edges of an undirected tree, is a special case of a multitree. The subgraph reachable from any vertex in a multitree is an arborescence rooted in the vertex, that is a polytree in which all edges are oriented away from the root.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (8)

Related concepts (6)

Related courses (3)

Related lectures (28)

Better Trees for Santa Claus

Etienne Michel François Bamas, Lars Rohwedder

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...

New York2023

On the Turan number of ordered forests

Gábor Tardos, Istvan Tomon, Dániel József Korándi

An ordered graph H is a simple graph with a linear order on its vertex set. The corresponding Turan problem, first studied by Pach and Tardos, asks for the maximum number ex(

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

Exact Synthesis of LTL Properties from Traces

Heinz Riener

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

Orientation (graph theory)

In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph. A directed graph is called an oriented graph if none of its pairs of vertices is linked by two symmetric edges. Among directed graphs, the oriented graphs are the ones that have no 2-cycles (that is at most one of (x, y) and (y, x) may be arrows of the graph). A tournament is an orientation of a complete graph. A polytree is an orientation of an undirected tree.

Polytree

In mathematics, and more specifically in graph theory, a polytree (also called directed tree, oriented tree or singly connected network) is a directed acyclic graph whose underlying undirected graph is a tree. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is both connected and acyclic. A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest.

Arborescence (graph theory)

In graph theory, an arborescence is a directed graph in which, for a vertex u (called the root) and any other vertex v, there is exactly one directed path from u to v. An arborescence is thus the directed-graph form of a rooted tree, understood here as an undirected graph. Equivalently, an arborescence is a directed, rooted tree in which all edges point away from the root; a number of other equivalent characterizations exist. Every arborescence is a directed acyclic graph (DAG), but not every DAG is an arborescence.

ME-427: Networked control systems

This course offers an introduction to control systems using communication networks for interfacing sensors, actuators, controllers, and processes. Challenges due to network non-idealities and opportun

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

MATH-506: Topology IV.b - cohomology rings

Singular cohomology is defined by dualizing the singular chain complex for spaces. We will study its basic properties, see how it acquires a multiplicative structure and becomes a graded commutative a

The Topological Künneth Theorem MATH-506: Topology IV.b - cohomology rings

Explores the topological Künneth Theorem, emphasizing commutativity and homotopy equivalence in chain complexes.

Untitled CS-250: Algorithms I