Algorithms for longest chains in pseudo-transitive graphs

MaRDI QIDQ5252023zbMATH OpenFDO

Authors Farhad Shahrokhi

Publication date 21 May 2015

Full work available at URL https://arxiv.org/abs/1701.05286

zbMATH Keywords

orderingpseudo-transitivity

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: A directed acyclic graph G = (V, E) is pseudo-transitive with respect to a given subset of edges E1, if for any edge ab in E1 and any edge bc in E, we have ac in E. We give algorithms for computing longest chains and demonstrate geometric applications that unify and improves some important past results. (For specific applications see the introduction.)

Recommendations

• An algorithm for transitive reduction of an acyclic graph
• Algorithms for transitive closure
• Speeding up dynamic transitive closure for bounded degree graphs
• scientific article; zbMATH DE number 3958732
• On the calculation of transitive reduction-closure of orders

Cited in

(3)

• scientific article; zbMATH DE number 5521183 (Why is no real title available?)
• Computing the all-pairs longest chains in the plane
• Strong pseudo transitivity and intersection graphs

This page was built for publication: Algorithms for longest chains in pseudo-transitive graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5252023)