Generating all the acyclic orientations of an undirected graph

被引：22

作者：

Barbosa, VC

Szwarcfiter, JL

机构：

[1] Fed Univ Rio De Janeiro, COPPE, BR-21945970 Rio De Janeiro, Brazil

[2] Fed Univ Rio De Janeiro, NCE, BR-20001970 Rio De Janeiro, Brazil

[3] COPPE, BR-20001970 Rio De Janeiro, Brazil

来源：

INFORMATION PROCESSING LETTERS | 1999年 / 72卷 / 1-2期

关键词：

acyclic orientations; algorithms; graphs;

D O I：

10.1016/S0020-0190(99)00120-9

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Let G be an undirected graph with n vertices, m edges and alpha acyclic orientations. We describe an algorithm for finding all these orientations in overall time O((n + m)alpha) and delay complexity O(n(n + m)). The space required is O(n + m). (C) 1999 Published by Elsevier Science B.V. All rights reserved.

引用

页码：71 / 74

页数：4

共 7 条

[1]

Barbosa V. C., 1993, MASSIVELY PARALLEL M

[2] CONCURRENCY IN HEAVILY LOADED NEIGHBORHOOD-CONSTRAINED SYSTEMS [J].

BARBOSA, VC ;

GAFNI, E .

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1989, 11 (04) :562-584

[3]

BARBOSA VC, 1996, ES40596 TR COPPEUFRJ

[4]

Knuth Donald E., 1973, ART COMPUTER PROGRAM, V1

[5] Generating the acyclic orientations of a graph [J].

Squire, MB .

JOURNAL OF ALGORITHMS, 1998, 26 (02) :275-290

[6]

Stanley R. P., 1973, Discrete Mathematics, V5, P171, DOI 10.1016/0012-365X(73)90108-8

[7]

VO KP, 1987, LINEAR MULTILINEAR A, V22, P161

← 1 →