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

DOI10.1016/J.COR.2011.05.019MaRDI QIDQ1762017zbMATH OpenOpenAlexFDO

Authors Yuma Tanaka, Shinji Imahori, Mihiro Sasaki, Mutsunori Yagiura

Publication date 15 November 2012

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2011.05.019

zbMATH Keywords

column generationsensor networkLP relaxationwireless ad hoc networkrelaxation heuristics

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Lagrangian-based column generation for the node capacitated in-tree packing problem
• The complexity of 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
• Integral packing of trees and branchings

Cites work

• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3285076 (Why is no real title available?)
• scientific article; zbMATH DE number 3373559 (Why is no real title available?)
• Arc-disjoint in-trees in directed graphs
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Network lifetime and power assignment in ad hoc wireless networks
• On a property of n-edge-connected digraphs
• Optimum branchings
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• The complexity of the node capacitated in-tree packing problem

Cited in

(2)

• The complexity of the node capacitated in-tree packing problem
• Lagrangian-based column generation for the node capacitated in-tree packing problem

This page was built for publication: An LP-based heuristic algorithm for 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 Q1762017)