✦ LIBER ✦

Deferred-query: An efficient approach for some problems on interval graphs

✍ Scribed by Chang, Maw-Shang; Peng, Sheng-Lung; Liaw, Jenn-Liang

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 99 KB
Volume: 34
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199908)34:1<1::aid-net1>3.0.co;2-c

No coin nor oath required. For personal study only.

✦ Synopsis

This paper introduces the idea of a deferred-query approach to design O(n) algorithms for the domatic partition, optimal path cover, Hamiltonian path, Hamiltonian circuit, and maximum matching problems on interval graphs given n endpoint-sorted intervals. The previous best-known algorithms run in O(n log log n) or O(n ϩ m) time, where m is the number of edges in the corresponding interval graphs.

📜 SIMILAR VOLUMES

A simpleO(n2) algorithm for the all-pair

A simpleO(n2) algorithm for the all-pairs shortest path problem on an interval graph

✍ Mirchandani, Prakash 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB 👁 2 views

Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O(n') algorithm for solving the all-pairs shortest path problem on graph G . A recent algorithm for this problem has the same time-complexity but is fairly complicated to describe. However, our a