The edge-orientation problem and some of its variants on weighted graphs

DOI10.1016/j.ins.2005.09.001zbMath1102.68099MaRDI QIDQ2509220

William Chung-Kung Yen

Publication date: 19 October 2006

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2005.09.001

zbMATH Keywords

directed graph; trees; NP-hard; undirected graph; special graphs; edge-orientation problem

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Series-parallel orientations preserving the cycle-radius

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On orientations and shortest paths
• On the orientation of graphs
• An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs
• Graph orientations with edge-connection and parity constraints
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Minimizing maximum indegree
• Conservative weightings and ear-decompositions of graphs
• On the degrees of the vertices of a directed graph
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• A Primal-Dual Algorithm for Submodular Flows
• Strongly connected orientations of mixed multigraphs
• A Strongly Polynomial Algorithm for Minimum Cost Submodular Flow Problems
• Robbins's Theorem for Mixed Multigraphs
• `` Strong NP-Completeness Results
• Locating replicas of a database on a network
• Centroids, Representations, and Submodular Flows
• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• An orientation theorem with parity conditions