.png){kind=icon}
.png){kind=icon}
Return
A faster algorithm for independent cut
.png){kind=icon}
OA
AI
DOI：10.1016/j.tcs.2025.115542.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The previously fastest algorithm for deciding the existence of an independent cut had a runtime of O & lowast;(1.4423(n)), where is the order of the input graph. We improve this to O & lowast;(1.4143). In fact, we prove a runtime of O & lowast;(2((1/2-Delta)n)) on graphs of order and maximum degree at most Delta, where alpha(Delta )= 1/2+4 & LeftFloor;Delta/2 & RightFloor; . Furthermore, we show that the problem is fixed-parameter tractable on graphs of order and minimum degree at least for some beta > 1/2, where is the parameter.
Keywords:
Independent cut
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
1
Papers:
248
Citations:
1.0W
Organization
No organization information available