Attention:The NSF Public Access Repository (PAR) system and access will be unavailable from 11:00 PM ET on Thursday, November 12th until 12:00 AM ET on Friday, November 13th due to maintenance. We apologize for the inconvenience.


Search for: All records

Creators/Authors contains: "Luu, Huong"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Abstract. In the spanning-tree congestion problem (STC), we are given a graph G, and the objective is to compute a spanning tree of G that minimizes the maximum edge congestion. While STC is known to be NP-hard, even for some restricted graph classes, several key questions regarding its computational complexity remain open, and we address some of these in our paper. (i) For graphs of degree at most d, it is known that STC is NP-hard when d ≥ 8. We provide a complete resolution of this variant, by showing that STC remains NP-hard for each degree bound d ≥ 3. (ii) In the decision version of STC, given an integer K, the goal is to determine whether the congestion of G is at most K. We prove that this variant is polynomial-time solvable for K-edge-connected graphs. 
    more » « less
    Free, publicly-accessible full text available May 1, 2027
  2. In the spanning-tree congestion problem (STC), we are given a graph G, and the objective is to compute a spanning tree of G that minimizes the maximum edge congestion. While STC is known to be NP-hard, even for some restricted graph classes, several key questions regarding its computational complexity remain open, and we address some of these in our paper. (i) For graphs of degree at most Δ, it is known that STC is NP-hard when Δ≥8. We provide a complete resolution of this variant, by showing that STC remains NP-hard for each degree bound Δ≥3. (ii) In the decision version of STC, given an integer K, the goal is to determine whether the congestion of G is at most K. We prove that this variant is polynomial-time solvable for K-edge-connected graphs. 
    more » « less
    Free, publicly-accessible full text available April 1, 2027
  3. Abstract Analysis of pipe networks involves computing flow rates and pressure differences on pipe segments in the network, given the external inflow/outflow values. This analysis can be conducted using iterative methods, among which the algorithms of Hardy Cross and Newton-Raphson have historically been applied in practice. In this note, we address the mathematical analysis of the local convergence of these algorithms. The loop-based Newton–Raphson algorithm converges quadratically fast, and we provide estimates for its convergence radius to correct some estimates in the previous literature. In contrast, we show that the convergence of the Hardy Cross algorithm is only linear. This provides theoretical confirmation of experimental observations reported earlier in the literature. 
    more » « less
  4. Abstract In the spanning tree congestion problem, given a connected graphG, the objective is to compute a spanning treeTinGthat minimizes its maximum edge congestion, where the congestion of an edgeeofTis the number of edges inGfor which the unique path inTbetween their endpoints traversese. The problem is known to be$$\mathbb{N}\mathbb{P}$$ NP -hard, but its approximability is still poorly understood, and it is not even known whether the optimum solution can be efficiently approximated with ratioo(n). In the decision version of this problem, denoted$${\varvec{K}-\textsf {STC}}$$ K-STC , we need to determine ifGhas a spanning tree with congestion at mostK. It is known that$${\varvec{K}-\textsf {STC}}$$ K-STC is$$\mathbb{N}\mathbb{P}$$ NP -complete for$$K\ge 8$$ K≥8 , and this implies a lower bound of 1.125 on the approximation ratio of minimizing congestion. On the other hand,$${\varvec{3}-\textsf {STC}}$$ 3-STC can be solved in polynomial time, with the complexity status of this problem for$$K\in { \left\{ 4,5,6,7 \right\} }$$ K∈4,5,6,7 remaining an open problem. We substantially improve the earlier hardness results by proving that$${\varvec{K}-\textsf {STC}}$$ K-STC is$$\mathbb{N}\mathbb{P}$$ NP -complete for$$K\ge 5$$ K≥5 . This leaves only the case$$K=4$$ K=4 open, and improves the lower bound on the approximation ratio to 1.2. Motivated by evidence that minimizing congestion is hard even for graphs of small constant radius, we also consider$${\varvec{K}-\textsf {STC}}$$ K-STC restricted to graphs of radius 2, and we prove that this variant is$$\mathbb{N}\mathbb{P}$$ NP -complete for all$$K\ge 6$$ K≥6 . 
    more » « less