Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs

DOI10.1016/J.JCTB.2008.01.006MaRDI QIDQ958684zbMATH OpenOpenAlexFDO

Authors Tamás Király, Lap Chi Lau

Publication date 8 December 2008

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2008.01.006

zbMATH Keywords

hypergraphorientationSteiner tree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Hypergraphs (05C65)

Recommendations

• scientific article; zbMATH DE number 7053371
• Approximating node connectivity problems via set covers
• An approximate max-Steiner-tree-packing min-Steiner-cut theorem

Cites work

• scientific article; zbMATH DE number 446490 (Why is no real title available?)
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 1305440 (Why is no real title available?)
• scientific article; zbMATH DE number 1146228 (Why is no real title available?)
• scientific article; zbMATH DE number 1146232 (Why is no real title available?)
• scientific article; zbMATH DE number 2079349 (Why is no real title available?)
• A Reduction Method for Edge-Connectivity in Graphs
• Algorithmic construction of sets for k -restrictions
• An Algorithm for Submodular Functions on Graphs
• Approximating theDomatic Number
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Combined connectivity augmentation and orientation problems
• Edge-Disjoint Spanning Trees of Finite Graphs
• Edge-disjoint trees containing some given vertices in a graph
• On Orientations, Connectivity and Odd-Vertex-Pairings in Finite Graphs
• On the Problem of Decomposing a Graph into n Connected Factors
• On the degrees of the vertices of a directed graph
• On the orientation of graphs
• On the orientation of graphs and hypergraphs
• Packing Steiner Forests

Cited in

(6)

• On orienting graphs for connectivity: Projective planes and Halin graphs
• Graph orientations with set connectivity requirements
• Steiner connectivity problems in hypergraphs
• Rooted \(k\)-connections in digraphs
• On Eulerian orientations of even-degree hypercubes
• Decreasing minimization on M-convex sets: algorithms and applications

This page was built for publication: Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs

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