Polynomial algorithms for canonical forms of orientations

DOI10.1007/S10878-014-9735-ZMaRDI QIDQ5963618zbMATH OpenOpenAlexFDO

Authors Martin Kochol

Publication date 23 February 2016

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-014-9735-z

zbMATH Keywords

flowsearch algorithmtension and Tutte polynomialstotally cyclic and acyclic orientation

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Tension-flow polynomials on graphs
• A bijection for Eulerian-equivalence classes of totally cyclic orientations
• Generating the Acyclic Orientations of a Graph
• Bipolar orientations revisited
• scientific article; zbMATH DE number 17787

Cites work

• A bijection for Eulerian-equivalence classes of totally cyclic orientations
• Bounds on the coefficients of tension and flow polynomials
• Depth-First Search and Linear Graph Algorithms
• Digraphs
• Ehrhart theory, modular flow reciprocity, and the Tutte polynomial
• Inside-out polytopes
• Nowhere-harmonic colorings of graphs
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• Orientations, lattice polytopes, and group arrangements I: Chromatic and tension polynomials of graphs
• Polynomials associated with nowhere-zero flows
• Tension polynomials of graphs

Cited in

(4)

• Interpretations of the Tutte and characteristic polynomials of matroids
• Algorithms to solve absolute orientation problem for GL(3), O(3), and SO(3) groups
• Computing Canonical Polygonal Schemata with Generalized Maps
• Interpretations of the Tutte polynomials of regular matroids

This page was built for publication: Polynomial algorithms for canonical forms of orientations

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