On the complexity of finding well-balanced orientations with upper bounds on the out-degrees

DOI10.1007/S10878-022-00962-YMaRDI QIDQ2106523zbMATH OpenOpenAlexFDO

Authors Florian Hoersch, Zoltán Szigeti

Publication date 16 December 2022

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2202.13759

zbMATH Keywords

complexitygraph orientationwell-balanced

Mathematics Subject Classification ID

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

Recommendations

• On finding orientations with the fewest number of vertices with small out-degree
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• Approximating upper degree-constrained partial orientations
• The complexity of two graph orientation problems
• Simultaneous well-balanced orientations of graphs
• Planar orientations with low out-degree and compaction of adjacency matrices
• Approximation algorithms and hardness results for shortest path based graph orientations
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree

Cites work

• scientific article; zbMATH DE number 446490 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Reduction Method for Edge-Connectivity in Graphs
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Connections in combinatorial optimization
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• On the orientation of graphs
• Recent results on well-balanced orientations
• Well-balanced orientations of mixed graphs

Cited in

(7)

• On finding orientations with the fewest number of vertices with small out-degree
• Recent results on well-balanced orientations
• Simultaneous well-balanced orientations of graphs
• On the most imbalanced orientation of a graph
• Orientations of graphs with prescribed weighted out-degrees
• On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
• On orientations maximizing total arc-connectivity

Describes a project that uses

Uses Software

• EGRES

This page was built for publication: On the complexity of finding well-balanced orientations with upper bounds on the out-degrees

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