Degree-constrained graph orientation: maximum satisfaction and minimum violation
From MaRDI portal
Publication:260260
DOI10.1007/s00224-014-9565-5zbMath1332.05059OpenAlexW2044147076MaRDI QIDQ260260
Jesper Jansson, Eiji Miyano, Yuichi Asahiro, Hirotaka Ono
Publication date: 21 March 2016
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-014-9565-5
Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)
Related Items
Parameterized orientable deletion, Orienting undirected phylogenetic networks, Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity, Graph orientation with splits, Unnamed Item, Upper and lower degree-constrained graph orientation with minimum penalty
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
- On the hardness of approximating minimum vertex cover
- Planar orientations with low out-degree and compaction of adjacency matrices
- A polynomial time primal network simplex algorithm for minimum cost flows
- An analysis of the greedy algorithm for the submodular set covering problem
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Minimizing maximum indegree
- Complexity of approximating bounded variants of optimization problems
- Graph balancing: a special case of scheduling unrelated parallel machines
- On the degrees of the vertices of a directed graph
- Acyclic orientations of graphs
- GRAPH ORIENTATION TO MAXIMIZE THE MINIMUM WEIGHTED OUTDEGREE
- Beyond the flow decomposition barrier
- On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
- GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
- Upper degree-constrained partial orientations
- Strongly connected orientations of mixed multigraphs
- Approximating Maximum Clique by Removing Subgraphs
- Non-approximability results for optimization problems on bounded degree instances
- Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
- Max flows in O(nm) time, or better
- Graph Orientations Optimizing the Number of Light or Heavy Vertices
