On finding orientations with the fewest number of vertices with small out-degree

DOI10.1016/J.DAM.2015.05.007zbMATH Open1319.05126arXiv1410.8154OpenAlexW912673598MaRDI QIDQ494438FDOQ494438

Authors: Kaveh Khoshkhah 

Publication date: 1 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Given an undirected graph, each of the two end-vertices of an edge can own the edge. Call a vertex poor, if it owns at most one edge. We give a polynomial time algorithm for the problem of finding an assignment of owners to the edges which minimizes the number of poor vertices. In the terminology of graph orientation, this means finding an orientation for the edges of a graph minimizing the number of edges with out-degree at most 1, and answers a question of Asahiro Jansson, Miyano, Ono (2014).

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

Recommendations

• On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Planar orientations with low out-degree and compaction of adjacency matrices
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• Minimizing and maximizing the diameter in orientations of graphs
• scientific article; zbMATH DE number 3991541
• Approximation algorithms and hardness results for shortest path based graph orientations
• Orientations of graphs with prescribed weighted out-degrees
• Algorithms for finding a rooted \((k,1)\)-edge-connected orientation

zbMATH Keywords

graph algorithmsgraph orientation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Graph orientations optimizing the number of light or heavy vertices
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Degree-constrained graph orientation: maximum satisfaction and minimum violation

Cited In (5)

• On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
• Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
• Planar orientations with low out-degree and compaction of adjacency matrices
• Graph orientation with splits
• Egalitarian graph orientations

This page was built for publication: On finding orientations with the fewest number of vertices with small out-degree

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