Split (graph theory)
id:
split-graph-theory-321-15431006
title:
Split (graph theory)
text:
In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms. Splits and split decompositions were first
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Split_(graph_theory)
date created:
date modified:
2023-11-08T00:18:08Z
main entity:
{"identifier":"Q25352092","url":"https://www.wikidata.org/entity/Q25352092"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/e/e2/Split_decomposition.svg","width":540,"height":504}
fields total:
13
integrity:
14