Transitive Orientations of Graphs

descriptionPublicationkeyboard_double_arrow_right Article 01 Dec 1988 English Publisher:Society for Industrial & Applied Mathematics (SIAM)Journal:SIAM Journal on Computing, volume 17, pages 1,119-1,133 (issn: 0097-5397, eissn: 1095-7111,

Copyright policy )

Authors: Béla Bollobás; Graham R. Brightwell;

doi: 10.1137/0217072

Transitive Orientations of Graphs

- Summary
- Subjects
- Metrics

Abstract

Consider an acyclic orientation of the edges of a graph G of order n and relative size p. The partial order obtained by transitive closure is called the transitive orientation of G. Let t(G) be the maximum number of unrelated pairs for different orders, and t(n,p) its minimum over G for fixed n and p. Bounds on t(n,p) are given throughout the range of \(p=p(n)\).

Related Organizations

University of Cambridge
United Kingdom

Keywords

orientations, Graph theory (including graph drawing) in computer science, Analysis of algorithms and problem complexity, Random graphs (graph-theoretic aspects), partial order, sorting

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	1
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average