Algorithms for interval catch digraphs

DOI10.1016/0166-218X(94)90104-XzbMath0810.68104MaRDI QIDQ1329814

Erich Prisner

Publication date: 4 April 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

interval catch digraphsinterval nest digraphsnest representation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Related Items

Unnamed Item, Max point-tolerance graphs, Representing digraphs using intervals or circular arcs, Proper and unit bitolerance orders and graphs, On the kernel and related problems in interval digraphs, Classes of intersection digraphs with good algorithmic properties, Intersection representation of digraphs in trees with few leaves, The distribution of the relative arc density of a family of interval catch digraph based on uniform data, The distribution of the domination number of class cover catch digraphs for non-uniform one-dimensional data, On the distribution of the domination number for random class cover catch digraphs, Domination number of an interval catch digraph family and its use for testing uniformity, Uniquely Restricted Matchings in Interval Graphs, Homogeneously Representable Interval Bigraphs, Chronological Orderings of Interval Digraph

Uses Software

• PARTITION

Cites Work

• Unnamed Item
• Unnamed Item
• On kernels and semikernels of digraphs
• A characterization of interval catch digraphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• An efficient algorithm for finding a two-pair, and its applications
• Optimizing weakly triangulated graphs
• A digraph represented by a family of boxes or spheres
• Interval digraphs: An analogue of interval graphs