Concept
Tree-depth
Related publications (14)
Tree in Tree: from Decision trees to Decision Graphs
Decision trees have been widely used as classifiers in many machine learning applications thanks to their lightweight and interpretable decision process. This paper introduces Tree in Tree decision graph (TnT), a framework that extends the conventional dec ...
Curran Associates, Inc, (NIPS '21: Proceedings of the 35th International Conference on Neural Information Processing Systems)2021New Results in Integer and Lattice Programming
An integer program (IP) is a problem of the form , where , , , and is a separable convex objective function.
The problem o ...
EPFL2020Simple Realizability of Complete Abstract Topological Graphs Simplified
An abstract topological graph (briefly an AT-graph) is a pair A = (G, X) where G = (V, E) is a graph and X. E2 is a set of pairs of its edges. The AT-graph A is simply realizable if G can be drawn in the plane so that each pair of edges from X crosses exac ...
SPRINGER2020Scaling Similarity Joins over Tree-Structured Data
Given a large collection of tree-structured objects (e.g., XML documents), the similarity join finds the pairs of objects that are similar to each other, based on a similarity threshold and a tree edit distance measure. The state-of-the-art similarity join ...
Assoc Computing Machinery2015Decomposition and tractability in qualitative spatial and temporal reasoning
Constraint networks in qualitative spatial and temporal reasoning (QSTR) typically feature variables defined on infinite domains. Mainstream algorithms for deciding network consistency are based on searching for network refinements whose consistency is kno ...
Elsevier2013Characterizing Path Graphs by Forbidden Induced Subgraphs
A path graph is the intersection graph of subpaths of a tree. In 1970, Renz asked for a characterization of path graphs by forbidden induced subgraphs. We answer this question by determining the complete list of graphs that are not path graphs and are mini ...
2009Polarity of chordal graphs
Dominique de Werra, Tinaz Ekim
Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, th ...
2008Polar cographs
Dominique de Werra, Tinaz Ekim
Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s, k)-polar if there exists a partition A, B of its vertex set such that A induces a complete s-partite grap ...
Elsevier2008An introduction to treewidth
The notion of treewidth has seen to be a powerful vehicle for many graph algorithmic studies. A lot of problems, which are in general -complete, can be solved in polynomial time for graphs with small treewidth. In the first part of this paper we presen ...
2006