In a graph, a matching cut is an edge cut that is a matching. Matching Cut is the problem of deciding whether or not a given graph has a matching cut, which is known to be $${\mathsf {NP}}$$NP -complete. While Matching Cut is trivial for graphs with minimum degree at most one, it is $${\mathsf {NP}}$$NP -complete on graphs with minimum degree two. In this paper, we show that, for any given constant $$c>1$$c > 1 , Matching Cut is $${\mathsf {NP}}$$NP -complete in the class of graphs with minimum degree c and this restriction of Matching Cut has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant $$\epsilon >0$$ϵ > 0 , Matching Cut remains $${\mathsf {NP}}$$NP -complete in the class of n-vertex (bipartite) graphs with unbounded minimum degree $$\delta >n^{1-\epsilon }$$δ > n 1 - ϵ . We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree $$\delta \ge 3$$δ ≥ 3 in $$O^*(\lambda ^n)$$O ∗ ( λ n ) time, where $$\lambda$$λ is the positive root of the polynomial $$x^{\delta +1}-x^{\delta }-1$$x δ + 1 - x δ - 1 . Despite the hardness results, this is a very fast exact exponential-time algorithm for Matching Cut on graphs with large minimum degree; for instance, the running time is $$O^*(1.0099^n)$$O ∗ ( 1 . 0099 n ) on graphs with minimum degree $$\delta \ge 469$$δ ≥ 469 . Complementing our hardness results, we show that, for any two fixed constants $$1< c <4$$1 < c < 4 and $$c^{\prime }\ge 0$$c ′ ≥ 0 , Matching Cut is solvable in polynomial time for graphs with large minimum degree $$\delta \ge \frac{1}{c}n-c^{\prime }$$δ ≥ 1 c n - c ′ .

Background and Objective: In the first trimester of pregnancy, fetal growth, and abnormalities can be assessed using the exact middle sagittal plane (MSP) of the fetus. However, the ultrasound (US) image quality and operator experience affect the accuracy. We present an automatic system that enables precise fetal MSP detection from three-dimensional (3D) US and provides an evaluation of its performance using a generative adversarial network (GAN) framework. Method: The neural network is designed as a filter and generates masks to obtain the MSP, learning the features and MSP location in 3D space. Using the proposed image analysis system, a seed point was obtained from 218 first-trimester fetal 3D US volumes using deep learning and the MSP was automatically extracted. Results: The experimental results reveal the feasibility and excellent performance of the proposed approach between the automatically and manually detected MSPs. There was no significant difference between the semi-automatic and automatic systems. Further, the inference time in the automatic system was up to two times faster than the semi-automatic approach. Conclusion: The proposed system offers precise fetal MSP measurements. Therefore, this automatic fetal MSP detection and measurement approach is anticipated to be useful clinically. The proposed system can also be applied to other relevant clinical fields in the future.

This work investigates divisible load distribution using multi-installment processing on complete b -ary tree networks. Classic methods of distributing a divisible load divide the computation and communication processes into multiple time intervals in a pipelined fashion. The algorithm $\mathbb {M}$ ( m ulti-installment) herein uses multi-installment processing with pipelined communication to reduce the initial distribution time and to improve the performance. Closed-form expressions for the parallel processing time and speed-up are derived. This work reveals that the asymptotic speed-up of the proposed algorithm is $b\beta +1$ where $\beta$ is the computation-to-communication ratio of a node in the system. Algorithm $\mathbb {M}$ outperforms the classic algorithm in all cases. The algorithm $\mathbb {S}$ ( s tart-up cost) that is developed herein includes the computation and communication start-up costs. Finally, two algorithms $\mathbb {M}$ and $\mathbb {S}$ are combined to form algorithm $\mathbb {MS}$ with even better performance than each.

The problem of scheduling malleable tasks with precedence constraints is one of the most important strongly \mathcal{NP}-hard problems, given m identical processors and n tasks. A malleable task is one that runs in parallel on a varying number of processors. In addition, the processing sequences of tasks are constrained by the precedence constraints. The goal is to find a feasible schedule that minimizes the makespan (maximum completion time). This article presents an iterative method for improving the performance ratio of scheduling malleable tasks. The proposed algorithm achieves an approximation ratio of 4.4841 after 2 iterations. This improves the so far best-known factor of 4.7306 due to Jansen and Zhang. For a large number of iterations (>100), the approximation ratio of the proposed algorithm is tends toward $2+\sqrt{2}\approx 3.4143$.

Background: Improper endotracheal tube (ETT) positioning is frequently observed and potentially hazardous in the intensive care unit. The authors developed a deep learning–based automatic detection algorithm detecting the ETT tip and carina on portable supine chest radiographs to measure the ETT–carina distance. This study investigated the hypothesis that the algorithm might be more accurate than frontline critical care clinicians in ETT tip detection, carina detection, and ETT–carina distance measurement. Methods: A deep learning–based automatic detection algorithm was developed using 1,842 portable supine chest radiographs of 1,842 adult intubated patients, where two board-certified intensivists worked together to annotate the distal ETT end and tracheal bifurcation. The performance of the deep learning–based algorithm was assessed in 4-fold cross-validation (1,842 radiographs), external validation (216 radiographs), and an observer performance test (462 radiographs) involving 11 critical care clinicians. The performance metrics included the errors from the ground truth in ETT tip detection, carina detection, and ETT–carina distance measurement. Results: During 4-fold cross-validation and external validation, the median errors (interquartile range) of the algorithm in ETT–carina distance measurement were 3.9 (1.8 to 7.1) mm and 4.2 (1.7 to 7.8) mm, respectively. During the observer performance test, the median errors (interquartile range) of the algorithm were 2.6 (1.6 to 4.8) mm, 3.6 (2.1 to 5.9) mm, and 4.0 (1.7 to 7.2) mm in ETT tip detection, carina detection, and ETT–carina distance measurement, significantly superior to that of 6, 10, and 7 clinicians (all P < 0.05), respectively. The algorithm outperformed 7, 3, and 0, 9, 6, and 4, and 5, 5, and 3 clinicians (all P < 0.005) regarding the proportions of chest radiographs within 5 mm, 10 mm, and 15 mm error in ETT tip detection, carina detection, and ETT–carina distance measurement, respectively. No clinician was significantly more accurate than the algorithm in any comparison. Conclusions: A deep learning–based algorithm can match or even outperform frontline critical care clinicians in ETT tip detection, carina detection, and ETT–carina distance measurement. Editor’s Perspective: What We Already Know about This Topic: What This Article Tells Us That Is New:

This paper addresses the scheduling problem of coflows in identical parallel networks, a well-known N P-hard problem. We consider both flow-level scheduling and coflow-level scheduling problems. In the flow-level scheduling problem, flows within a coflow can be transmitted through different network cores, while in the coflow-level scheduling problem, flows within a coflow must be transmitted through the same network core. The key difference between these two problems lies in their scheduling granularity. Previous approaches relied on linear programming to solve the scheduling order. In this paper, we enhance the efficiency of solving by utilizing the primal-dual method. For the flow-level scheduling problem, we propose an approximation algorithm that achieves approximation ratios of $6-\frac{2}{m}$ and $5-\frac{2}{m}$ for arbitrary and zero release times, respectively, where m represents the number of network cores. Additionally, for the coflow-level scheduling problem, we introduce an approximation algorithm that achieves approximation ratios of 4m + 1 and 4m for arbitrary and zero release times, respectively. The algorithm presented in this paper has practical applications in data centers, such as those operated by Google or Facebook. The simulated results demonstrate the superior performance of our algorithms compared to previous approach, emphasizing their practical utility.