For k-chordal graphs it builds O(1)-round shortcuts of quality O(kD), and for diameter 3 and 4 it builds shortcuts of quality O~(n^{1/4}) and O~(n^{1/3}) that yield matching MST algorithms.
Intersection Graphs: An Introduction
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Intersection graphs are very important in both theoretical as well as application point of view. Depending on the geometrical representation, different type of intersection graphs are defined. Among them interval, circular-arc, permutation, trapezoid, chordal, disk, circle graphs are more important. In this article, a brief introduction of each of these intersection graphs is given. Some basic properties and algorithmic status of few problems on these graphs are cited. This article will help to the beginners to start work in this direction. Since the article contains a lot of information in a compact form it is also useful for the expert researchers too.
fields
cs.DC 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Low-Congestion Shortcut and Graph Parameters
For k-chordal graphs it builds O(1)-round shortcuts of quality O(kD), and for diameter 3 and 4 it builds shortcuts of quality O~(n^{1/4}) and O~(n^{1/3}) that yield matching MST algorithms.