Graph orientation with edge modifications

DOI10.1142/S012905412150012XMaRDI QIDQ5859684zbMATH OpenOpenAlexFDO

Authors Yuichi Asahiro, Jesper Jansson, Hirotaka Ono, T. P. Sandhya, 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 complexitygraph orientationinapproximabilityload balancingmaximum flow

Mathematics Subject Classification ID

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

Recommendations

• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Graph orientation to maximize the minimum weighted outdegree
• Upper and lower degree-constrained graph orientation with minimum penalty

Cites work

• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Correlation clustering
• Egalitarian graph orientations
• General factors of graphs
• Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
• Graph orientation to maximize the minimum weighted outdegree
• Graph orientation with splits
• Graph orientations optimizing the number of light or heavy vertices
• scientific article; zbMATH DE number 2185626 (Why is no real title available?)
• Introduction to algorithms.
• Max flows in O(nm) time, or better
• Minimizing maximum indegree
• Planar orientations with low out-degree and compaction of adjacency matrices
• The factorization of graphs. II

Cited in

(3)

• Graph orientation with edge modifications
• Pushing vertices and orienting edges
• A note on graph balancing problems with restrictions

This page was built for publication: Graph orientation with edge modifications

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