Affordable Access

Publisher Website

On minimal augmentation of a graph to obtain an interval graph

Authors
Journal
Journal of Computer and System Sciences
0022-0000
Publisher
Elsevier
Publication Date
Volume
22
Issue
1
Identifiers
DOI: 10.1016/0022-0000(81)90022-2
Disciplines
  • Computer Science

Abstract

Abstract This paper deals with the problem of adding edges to a graph such that the resulting graph becomes an interval graph. The set of edges added is called an augmentation. An algorithm is presented to find a minimal augmentation which runs in a time proportional to the product of the number of vertices and the number of edges of the resulting graph.

There are no comments yet on this publication. Be the first to share your thoughts.