The hypergraph orientation problem with vertex constraints

DOI10.1016/J.DAM.2026.01.003MaRDI QIDQ6854624zbMATH OpenFDO

Authors Alberto José Ferrari, V. Leoni, G. Nasini, Gabriel Valiente

Publication date 24 February 2026

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

Full work available at URL https://doi.org/10.1016/J.DAM.2026.01.003

zbMATH Keywords

optimizationcomputational complexityinteger programminggraph algorithmsmetabolic networksmetabolic pathways

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Integer programming (90C10) Hypergraphs (05C65) Genetics and population dynamics (92D99)

Cites work

• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing Eulerian trails
• Connections in combinatorial optimization
• Degree-constrained graph orientation: maximum satisfaction and minimum violation
• Directed hypergraphs and applications
• Graph orientation with splits
• Matching, Euler tours and the Chinese postman
• Minimizing external vertices in hypergraph orientations
• Minimizing maximum indegree
• Node-and edge-deletion NP-complete problems
• On finding orientations with the fewest number of vertices with small out-degree
• On the orientation of graphs and hypergraphs

This page was built for publication: The hypergraph orientation problem with vertex constraints

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