𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Unit and proper bitolerance digraphs

✍ Scribed by Shull, Randy; Trenk, Ann N.

Book ID
101227400
Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
95 KB
Volume
24
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we prove that the following statements about a directed graph G are equivalent. (1) G is a unit bitolerance digraph, (2) G is a proper bitolerance digraph, and (3) the digraph obtained by reversing all arc directions of G is an interval catch digraph (also known as a point-core digraph). This result combined with known algorithms for recognizing interval catch digraphs, gives the first known polynomial-time algorithm for recognizing a class of (bi)tolerance digraphs.

πŸ“œ SIMILAR VOLUMES

Proper and unit bitolerance orders and g
Proper and unit bitolerance orders and graphs
✍ Kenneth P. Bogart; Garth Isaak πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 729 KB

We say any order ~ is a tolerance order on a set of vertices if we may assign to each vertex x an interval Ix of real numbers and a real number tx called a tolerance in such a way that x~,y if and only if the overlap of Ix and ly is less than the minimum of t~ and ty and the center of I~ is less tha

Proper and unit tolerance graphs
Proper and unit tolerance graphs
✍ Kenneth P. Bogart; Peter C. Fishburn; Garth Isaak; Larry Langley πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 985 KB
Unit and Proper Tube Orders
Unit and Proper Tube Orders
✍ Joshua D. Laison πŸ“‚ Article πŸ“… 2008 πŸ› Springer Netherlands 🌐 English βš– 399 KB
Proper and Unit Trapezoid Orders and Gra
Proper and Unit Trapezoid Orders and Graphs
✍ Kenneth P. Bogart; Rolf H. MΓΆhring; Stephen P. Ryan πŸ“‚ Article πŸ“… 1998 πŸ› Springer Netherlands 🌐 English βš– 847 KB
The proper experimental unit, once again
The proper experimental unit, once again
✍ Martin Kagan; Harold Lindman πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 491 KB