Single-entry single-exit

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Single-entry single-exit" – news · newspapers · books · scholar · JSTOR (April 2024)

In mathematics graph theory, a single-entry single-exit (SESE) region in a given graph is an ordered edge pair.

For example, with the ordered edge pair, (a, b) of distinct control-flow edges a and b where:

1. a dominates b
   
2. b postdominates a
   
3. Every cycle containing a also contains b and vice versa.

where a node x is said to dominate node y in a directed graph if every path from start to y includes x. A node x is said to postdominate a node y if every path from y to end includes x.

So, a and b refer to the entry and exit edge, respectively.

• The first condition ensures that every path from start into the region passes through the region’s entry edge, a.
• The second condition ensures that every path from inside the region to end passes through the region’s exit edge, b.
• The first two conditions are necessary but not enough to characterize SESE regions: since backedges do not alter the dominance or postdominance relationships, the first two conditions alone do not prohibit backedges entering or exiting the region.
• The third condition encodes two constraints: every path from inside the region to a point 'above' a passed through b, and every path from a point 'below' b to a point inside the region passes through a.^[1]

This graph theory-related article is a stub. You can help Wikipedia by expanding it.

• v
• t
• e