Generating the acyclic orientations of a graph

被引：13

作者：

Squire, MB ^{[1
]}

机构：

[1] IBM Corp, Dept C8KA, Res Triangle Pk, NC 27709 USA

来源：

JOURNAL OF ALGORITHMS | 1998年 / 26卷 / 02期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1006/jagm.1997.0891

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The acyclic orientations of a graph are related to its chromatic polynomial to its reliability, and to certain hyperplane arrangements. In this paper, an algorithm for listing the acyclic orientations of a graph is presented. The algorithm is shown to require O(n) time per acyclic orientation generated. This is the most efficient algorithm known for generating acyclic orientations. (C) 1998 Academic Press.

引用

页码：275 / 290

页数：16

共 27 条

[1]

BEYER T, 1989, UNPUB CONSTANT AVERA

[2] COUNTING LINEAR EXTENSIONS [J].