Degree-constrained graph orientation: maximum satisfaction and minimum violation
From MaRDI portal
Recommendations
- Degree-constrained graph orientation: maximum satisfaction and minimum violation
- Graph orientations optimizing the number of light or heavy vertices
- Graph orientations optimizing the number of light or heavy vertices
- Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
- Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
Cites work
- A polynomial time primal network simplex algorithm for minimum cost flows
- Acyclic orientations of graphs
- An analysis of the greedy algorithm for the submodular set covering problem
- Approximating Maximum Clique by Removing Subgraphs
- Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree
- Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
- Beyond the flow decomposition barrier
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Complexity of approximating bounded variants of optimization problems
- Connections in combinatorial optimization
- Graph balancing: a special case of scheduling unrelated parallel machines
- GRAPH ORIENTATION ALGORITHMS TO MINIMIZE THE MAXIMUM OUTDEGREE
- Graph orientation to maximize the minimum weighted outdegree
- Graph orientations optimizing the number of light or heavy vertices
- scientific article; zbMATH DE number 3604926 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Max flows in O(nm) time, or better
- Minimizing maximum indegree
- Network flows. Theory, algorithms, and applications.
- Non-approximability results for optimization problems on bounded degree instances
- On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
- On the degrees of the vertices of a directed graph
- On the hardness of approximating minimum vertex cover
- Planar orientations with low out-degree and compaction of adjacency matrices
- Strongly connected orientations of mixed multigraphs
- Upper degree-constrained partial orientations
Cited in
(13)- Upper and lower degree-constrained graph orientation with minimum penalty
- Parameterized orientable deletion
- Degree-constrained graph orientation: maximum satisfaction and minimum violation
- Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
- Parameterized orientable deletion
- Graph orientations optimizing the number of light or heavy vertices
- Graph orientations optimizing the number of light or heavy vertices
- Graph orientation with splits
- Orienting undirected phylogenetic networks
- On the existence of funneled orientations for classes of rooted phylogenetic networks
- The hypergraph orientation problem with vertex constraints
- Minimizing external vertices in hypergraph orientations
- Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
This page was built for publication: Degree-constrained graph orientation: maximum satisfaction and minimum violation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q260260)
