On the most imbalanced orientation of a graph

DOI10.1007/978-3-319-21398-9_2zbMATH Open1465.90112OpenAlexW1136962814MaRDI QIDQ3196369FDOQ3196369

Authors: Walid Ben-Ameur, Antoine Glorieux, José Neto 

Publication date: 29 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-21398-9_2

Recommendations

• On the most imbalanced orientation of a graph
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
• On imbalances in digraphs
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Title not available (Why is that?)
• Planar orientations with low out-degree and compaction of adjacency matrices
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• Strongly connected orientations of mixed multigraphs
• Title not available (Why is that?)
• The complexity of satisfiability problems
• Digraphs
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Balanced vertex-orderings of graphs
• Distances in orientations of graphs
• Complexity of approximating the oriented diameter of chordal graphs
• Degree-constrained graph orientation: maximum satisfaction and minimum violation
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• Computing and Combinatorics
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Graphs Suppressible to an Edge
• Realizing degree imbalances in directed graphs

Cited In (7)

• Title not available (Why is that?)
• On imbalances in oriented tripartite graphs
• On the most imbalanced orientation of a graph
• Realizing degree imbalances in directed graphs
• A full description of polytopes related to the index of the lowest nonzero row of an assignment matrix
• Complete formulations of polytopes related to extensions of assignment matrices
• Directing Road Networks by Listing Strong Orientations

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

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