An Efficient Method for Indexing All Topological Orders of a Directed Graph

DOI10.1007/978-3-319-13075-0_9MaRDI QIDQ2942618zbMATH OpenOpenAlexFDO

Authors Yuma Inoue, Shin-Ichi Minato

Publication date 11 September 2015

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-13075-0_9

zbMATH Keywords

decision diagramsenumerating algorithmsexperimental algorithmslinear extensionspermutationstopological orders

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20)

Recommendations

• On computing the number of topological orderings of a directed acyclic graph
• Evaluating topological ordering in directed acyclic graphs
• Ordering graphs with large eccentricity-based topological indices
• Topological orderings of weighted directed acyclic graphs
• Topologically indexable graphs
• Ordering graphs with small index and its application
• Ordering connected graphs by their Kirchhoff indices
• scientific article; zbMATH DE number 6004055
• On indexable graphs
• A dynamic topological sort algorithm for directed acyclic graphs

Cited in

(5)

• Chain graph models: topological sorting of meta-arrows and efficient construction of \(\mathcal B\)-essential graphs
• Classical length-5 pattern-avoiding permutations
• Topological orderings of weighted directed acyclic graphs
• On computing the number of topological orderings of a directed acyclic graph
• Decision diagrams for solving a job scheduling problem under precedence constraints

This page was built for publication: An Efficient Method for Indexing All Topological Orders of a Directed Graph

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