The complexity of the node capacitated in-tree packing problem

DOI10.1002/net.20476zbMath1243.05058OpenAlexW2029735353MaRDI QIDQ2892141

Mihiro Sasaki, Yuichiro Miyamoto, Yusuke Kobayashi, Shinji Imahori, Mutsunori Yagiura, Hideki Hashimoto

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) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Combinatorial aspects of packing and covering (05B40)

Related Items

An LP-based heuristic algorithm for the node capacitated in-tree packing problem

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• An LP-based heuristic algorithm for the node capacitated in-tree packing problem
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• A MATHEMATICAL PROGRAMMING APPROACH TO THE MULTI-ROUND TOPOLOGY CONSTRUCTION PROBLEM IN WIRELESS SENSOR NETWORKS
• Algorithms - ESA 2003

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