Graph Orientation with Edge Modifications

DOI10.1142/S012905412150012XzbMath1458.68138OpenAlexW3126821017MaRDI QIDQ5859684

T. P. Sandhya, Hirotaka Ono, Jesper Jansson, Yuichi Asahiro, Eiji Miyano

Publication date: 19 April 2021

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s012905412150012x

zbMATH Keywords

computational complexityload balancingmaximum flowinapproximabilitygraph orientation

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Flows in graphs (05C21)

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Correlation clustering
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• General factors of graphs
• Planar orientations with low out-degree and compaction of adjacency matrices
• Minimizing maximum indegree
• GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE
• Egalitarian Graph Orientations
• Max flows in O(nm) time, or better
• The factorization of graphs. II
• Graph Orientations Optimizing the Number of Light or Heavy Vertices
• Graph orientation with splits

This page was built for publication: Graph Orientation with Edge Modifications