On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
From MaRDI portal
Publication:2106523
DOI10.1007/S10878-022-00962-YOpenAlexW4311181646MaRDI QIDQ2106523FDOQ2106523
Authors: Florian Hoersch, Zoltán Szigeti 
Publication date: 16 December 2022
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2202.13759
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
Directed graphs (digraphs), tournaments (05C20) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07)
Cites Work
- Title not available (Why is that?)
- Connections in combinatorial optimization
- On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
- A Reduction Method for Edge-Connectivity in Graphs
- A Theorem on Graphs, with an Application to a Problem of Traffic Control
- Title not available (Why is that?)
- On the orientation of graphs
- Well-balanced orientations of mixed graphs
- Recent results on well-balanced orientations
Cited In (7)
- Recent results on well-balanced orientations
- On the most imbalanced orientation of a graph
- On orientations maximizing total arc-connectivity
- Simultaneous well-balanced orientations of graphs
- On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
- Orientations of graphs with prescribed weighted out-degrees
- On finding orientations with the fewest number of vertices with small out-degree
Uses Software
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)
