Top

Journal of Combinatorial Optimization

Published in:

01-01-2016

Polynomial algorithms for canonical forms of orientations

Author: Martin Kochol

Published in: Journal of Combinatorial Optimization | Issue 1/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We introduce canonical forms that represent certain equivalence classes of totally cyclic and acyclic orientations of graphs and present a polynomial algorithms for their constructions. The forms are used in new formulas evaluating tension and flow polynomials on graphs.

previous article On the computational complexity of bridgecard

next article Some Motzkin–Straus type results for non-uniform hypergraphs

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Bang-Jensen J, Gutin G (2007) Digraphs: theory, algorithms and applications. Springer, BerlinMATH

Beck M, Braun B (2012) Nowhere-harmonic colorings of graphs. Proc Am Math Soc 140:47–63MathSciNetCrossRefMATH

Beck M, Zaslavsky T (2006) Inside-out polytopes. Adv Math 205:134–162MathSciNetCrossRefMATH

Breuer F, Dall A (2011) Bounds on the coefficients of tension and flow polynomials. J Algebr Comb 33:465–482MathSciNetCrossRefMATH

Breuer F, Sanyal R (2012) Ehrhart theory, modular flow reciprocity, and the Tutte polynomial. Math Z 270:1–18MathSciNetCrossRefMATH

Chen B (2010) Orientations, lattice polytopes, and group arrangements I: chromatic and tension polynomials of graphs. Ann Comb 13:425–452MathSciNetCrossRefMATH

Chen B, Yang ALB, Zhang TYJ (2008) A bijection for Eulerian-equivalence classes of totally cyclic orientations. Graphs Combin 24:519–530MathSciNetCrossRefMATH

Greene C, Zaslavsky T (1983) On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs. Trans Am Math Soc 280:97–126MathSciNetCrossRefMATH

Kochol M (2002a) Polynomials associated with nowhere-zero flows. J Combin Theory B 84:260–269MathSciNetCrossRefMATH

Kochol M (2002b) Tension polynomials of graphs. J Graph Theory 40:137–146MathSciNetCrossRefMATH

Tarjan R (1972) Depth-first search and linear graph algorithms. SIAM J Comput 1:146–160MathSciNetCrossRefMATH

Title: Polynomial algorithms for canonical forms of orientations
Author: Martin Kochol
Publication date: 01-01-2016
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2016
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-014-9735-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2016

Two approximation algorithms for two-agent scheduling on parallel machines to minimize makespan

An inequality that relates the size of a bipartite graph with its order and restrained domination number

The blocking job shop with rail-bound transportation

Minimax regret vertex 2-sink location problem in dynamic path networks

On the computational complexity of bridgecard

An efficient algorithm for distance total domination in block graphs

Premium Partner