On the most imbalanced orientation of a graph

DOI10.1007/s10878-017-0117-1zbMath1421.90151OpenAlexW4231998560MaRDI QIDQ721946

Antoine Glorieux, José Neto, Walid Ben-Ameur

Publication date: 20 July 2018

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

Full work available at URL: https://doi.org/10.1007/s10878-017-0117-1

zbMATH Keywords

complexitygraph theorymixed integer programmingorientationcactuscutting plane algorithm(in)approximability

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Planar orientations with low out-degree and compaction of adjacency matrices
• Distances in orientations of graphs
• Grid minors of graphs on the torus
• Balanced vertex-orderings of graphs
• Designing Steiner Networks with Unicyclic Connected Components: An Easy Problem
• Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• Strongly connected orientations of mixed multigraphs
• Complexity of approximating the oriented diameter of chordal graphs
• Matching, Euler tours and the Chinese postman
• The complexity of satisfiability problems
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• Digraphs
• Graphs Suppressible to an Edge
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Realizing degree imbalances in directed graphs

This page was built for publication: On the most imbalanced orientation of a graph