Flow hypergraph reducibility

被引：2

作者：

Guedes, A. L. P. ^{[1
]}

Markenzon, L. ^{[2
]}

Faria, L. ^{[3
]}

机构：

[1] Univ Fed Parana, BR-80060000 Curitiba, Parana, Brazil

[2] Univ Fed Rio de Janeiro, BR-21941 Rio De Janeiro, Brazil

[3] Univ Estado Rio de Janeiro, Rio De Janeiro, Brazil

来源：

DISCRETE APPLIED MATHEMATICS | 2011年 / 159卷 / 16期

关键词：

Directed hypergraphs; Flowgraphs; Graph reducibility; DIRECTED HYPERGRAPHS; GRAPHS;

D O I：

10.1016/j.dam.2011.02.006

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Reducible flowgraphs were first defined by Allen in terms of intervals; another definition based on two flowgraph transformations was presented by Hecht and Ullman. In this paper, we extend the notion of reducibility to directed hypergraphs, proving that the interval and the transformation approaches preserve the equivalence when applied to this family. (C) 2011 Elsevier BM. All rights reserved.

引用

页码：1775 / 1785

页数：11

共 21 条

[1]

Allen Frances E., 1970, ACM SIGPLAN NOTICES, V5, P1, DOI DOI 10.1145/390013.808479

[2]

AUSIELLO G, 1985, ANN DISCRETE MATH, V25, P1

[3]

CHAWLA S, 2004, ICDE 04, P832

[4] Some properties of conversion [J].

Church, Alonzo ;

Rosser, J. B. .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1936, 39 (1-3) :472-482

[5] DIRECTED HYPERGRAPHS AND APPLICATIONS [J].

GALLO, G ;

LONGO, G ;

PALLOTTINO, S ;

NGUYEN, S .

DISCRETE APPLIED MATHEMATICS, 1993, 42 (2-3) :177-201

[6] A note on minimum makespan assembly plans [J].

Gallo, G ;

Scutellà, MG .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 142 (02) :309-320

[7]

GALLO G, 1989, ATT GIORN LAV AIRO 8, P217

[8]

GUEDES ALP, 2001, THESIS U FEDERAL RIO

[9]

Guedes André Luiz Pires, 2005, Pesqui. Oper., V25, P383

[10]

Hecht M. S., 1972, SIAM Journal on Computing, V1, P188, DOI 10.1137/0201014

← 1 2 3 →