The complexity of the node capacitated in-tree packing problem

DOI10.1002/NET.20476MaRDI QIDQ2892141zbMATH OpenOpenAlexFDO

Authors Yuichiro Miyamoto, Yusuke Kobayashi, Mihiro Sasaki, Shinji Imahori, Mutsunori Yagiura

Publication date 18 June 2012

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20476

zbMATH Keywords

computational complexitynetwork designsensor networkwireless ad hoc network

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of packing and covering (05B40)

Recommendations

• An LP-based heuristic algorithm for the node capacitated in-tree packing problem
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• On the tree packing problem
• Complexity of the packing coloring problem for trees
• Complexity of the Packing Coloring Problem for Trees
• Lagrangian-based column generation for the node capacitated in-tree packing problem
• Node-Packing Problems with Integer Rounding Properties
• scientific article; zbMATH DE number 2217849
• The \((K, k)\)-capacitated spanning tree problem

Cites work

• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A mathematical programming approach to the multi-round topology construction problem in wireless sensor networks
• An LP-based heuristic algorithm for the node capacitated in-tree packing problem
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Network lifetime and power assignment in ad hoc wireless networks
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(4)

• An LP-based heuristic algorithm for the node capacitated in-tree packing problem
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Lagrangian-based column generation for the node capacitated in-tree packing problem
• The multi-terminal vertex separator problem: total dual integrality and polytope composition

This page was built for publication: The complexity of the node capacitated in-tree packing problem

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