Open AccessOn best transitive approximations to simple graphs
Author(s) -
Steven Delvaux,
Leon Horsten
Publication year - 2004
Publication title -
acta informatica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.481
H-Index - 40
eISSN - 1432-0525
pISSN - 0001-5903
DOI - 10.1007/s00236-004-0144-0
Subject(s) - simple (philosophy) , transitive relation , theory of computation , transitive reduction , mathematical proof , mathematics , discrete mathematics , transitive closure , combinatorics , computer science , graph , algorithm , line graph , voltage graph , philosophy , epistemology , geometry
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom