In this paper, we study the aggregation problem with power control under the physical interference. The maximum power is bounded. The goal is to assign power to nodes and schedule transmissions toward the sink without physical interferences such that the total number of time slots is minimized....

For a connected graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$G=(V,E)$$</EquationSource> </InlineEquation> and a positive integral vertex weight function <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$w$$</EquationSource> </InlineEquation>, a max-min weight balanced connected <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$k$$</EquationSource> </InlineEquation>-partition of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$G$$</EquationSource> </InlineEquation>, denoted as <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$$BCP_k$$</EquationSource> </InlineEquation>, is a partition of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$$V$$</EquationSource> </InlineEquation> into <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$$k$$</EquationSource> </InlineEquation> disjoint vertex subsets <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$$(V_1,V_2,\ldots ,V_k)$$</EquationSource> </InlineEquation> such that each <InlineEquation ID="IEq9"> <EquationSource...</equationsource></inlineequation></equationsource></inlineequation></equationsource></inlineequation></equationsource></inlineequation></equationsource></inlineequation></equationsource></inlineequation></equationsource></inlineequation></equationsource></inlineequation></equationsource></inlineequation>

Using local search method, this paper provides a polynomial time approximation scheme for the minimum vertex cover problem on <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$d$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi>d</mi> </math> </EquationSource> </InlineEquation>-dimensional ball graphs where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$d \ge 3$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>d</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math> </EquationSource> </InlineEquation>. The key to the proof is a new separator theorem for ball graphs in higher dimensional space....</equationsource></equationsource></inlineequation></equationsource></equationsource></inlineequation>