Upper and lower degree-constrained graph orientation with minimum penalty

DOI10.1016/j.tcs.2021.11.019OpenAlexW4200519638MaRDI QIDQ2062132

Jesper Jansson, Hirotaka Ono, Eiji Miyano, Yuichi Asahiro

Publication date: 22 December 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.11.019

zbMATH Keywords

treetreewidthpenalty functioninapproximabilitygraph orientationdegree constraint

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (4)

Parameterized orientable deletion ⋮ A connection between sports and matroids: how many teams can we beat? ⋮ Degree-constrained orientations of embedded graphs ⋮ Density decompositions of networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Degree-constrained graph orientation: maximum satisfaction and minimum violation
• Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
• Approximation algorithms for scheduling unrelated parallel machines
• Graph minors. III. Planar tree-width
• On the hardness of approximating minimum vertex cover
• On the parameterized complexity of multiple-interval graph problems
• Planar orientations with low out-degree and compaction of adjacency matrices
• S-functions for graphs
• Treewidth. Computations and approximations
• Time bounds for selection
• A 3/2-approximation algorithm for the graph balancing problem with two weights
• Graph balancing: a special case of scheduling unrelated parallel machines
• On the degrees of the vertices of a directed graph
• Iterative Methods in Combinatorial Optimization
• Solving the Convex Cost Integer Dual Network Flow Problem
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
• Capacitated Domination and Covering: A Parameterized Perspective
• Upper degree-constrained partial orientations
• Route-Enabling Graph Orientation Problems
• Faster Scaling Algorithms for Network Problems
• On independent sets, 2-to-2 games, and Grassmann graphs
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Theorem on Graphs, with an Application to a Problem of Traffic Control

This page was built for publication: Upper and lower degree-constrained graph orientation with minimum penalty