Publication

An introduction to treewidth

2006
Reports

Abstract

The notion of treewidth has seen to be a powerful vehicle for many graph algorithmic studies. A lot of problems, which are in general $NP$ -complete, can be solved in polynomial time for graphs with small treewidth. In the first part of this paper we present three different definitions of treewidth and we show their equivalence. The second part consists of an overview of the complexity status of the treewidth problem as well as of algorithmics results. We also discuss a polynomial time algorithm for computing the treewidth of circle graphs.

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.

2006
Reports

Abstract

Official source

Related concepts (32)

Treewidth

In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly k are called k-trees, and the graphs with treewidth at most k are called partial k-trees. Many other well-studied graph families also have bounded treewidth.

Tree-depth

In graph theory, the tree-depth of a connected undirected graph is a numerical invariant of , the minimum height of a Trémaux tree for a supergraph of . This invariant and its close relatives have gone under many different names in the literature, including vertex ranking number, ordered chromatic number, and minimum elimination tree height; it is also closely related to the cycle rank of directed graphs and the star height of regular languages.

List of graphs

This partial list of graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as vertex and path, see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see . Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer.

Related publications (32)

An introduction to treewidth

Chat with Graph Search

Time-Space Trade-Offs for Sumcheck

Probabilistic Methods for Joint Eigenvalue Problems with Applications

Sublinear Time Algorithms for Structured Matrices