On best transitive approximations to simple graphs

被引：9

作者：

Delvaux, S ^{[1
]}

Horsten, L

机构：

[1] Catholic Univ Louvain, Dept Comp Sci, B-3000 Louvain, Belgium

[2] Catholic Univ Louvain, Dept Philosophy, B-3000 Louvain, Belgium

来源：

ACTA INFORMATICA | 2004年 / 40卷 / 09期

关键词：

Simple Proof; Simple Graph; Complexity Aspect; Transitive Approximation;

D O I：

10.1007/s00236-004-0144-0

中图分类号：

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

学科分类号：

0812 ;

摘要：

In this paper, we investigate both combinatorial and complexity aspects of the problem of finding best transitive approximations to simple graphs. These problems are addressed in an interlocked way. We provide new and simple proofs of known results and in addition prove some new theorems.

引用

页码：637 / 655

页数：19

共 10 条

[1]

BLUM N, 1990, LECT NOTES COMPUT SC, V443, P586

[2]

DECLERCQ R, IN PRESS SYNTHESE

[3]

Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1

[4]

KRANTZ S, 2002, LOGIC PROOF TECHNIQU

[5] NP-HARD PROBLEMS IN HIERARCHICAL-TREE CLUSTERING [J].

KRIVANEK, M ;

MORAVEK, J .

ACTA INFORMATICA, 1986, 23 (03) :311-323

[6] A NOTE ON APPROXIMATING SYMMETRIC RELATIONS BY EQUIVALENCE RELATIONS [J].

MOON, JW .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1966, 14 (02) :226-&

[7]

Tomescu I, 1974, Discrete Math, V10, P173

[8] CRITERIA OF IDENTITY AND THE AXIOM OF CHOICE [J].

WILLIAMSON, T .

JOURNAL OF PHILOSOPHY, 1986, 83 (07) :380-394

[9]

Williamson T., 1990, IDENTITY DISCRIMINAT

[10]

ZAHN CT, 1964, SIAM J APPL MATH, V12, P840

← 1 →