消息灵通
发表于 2025-3-23 13:40:38
,On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem,emand vertices . with demands ., and costs and capacities for each edge. The goal is to find a minimum cost flow that satisfies the demands, respects the capacities and induces a (strongly) connected subgraph. This generalizes previously studied problems like the ...We study the parameterized comple
厚脸皮
发表于 2025-3-23 17:16:00
http://reply.papertrans.cn/39/3881/388038/388038_12.png
不舒服
发表于 2025-3-23 19:35:54
Disjoint Stable Matchings in Linear Time,cal results: .Moreover, we also give an algorithm to enumerate all maximum-length chains of disjoint stable matchings in the lattice of stable matchings of a given instance. This algorithm takes time polynomial in the input size for enumerating each chain. We also derive the expected number of such
轻快走过
发表于 2025-3-23 22:18:24
http://reply.papertrans.cn/39/3881/388038/388038_14.png
恭维
发表于 2025-3-24 05:32:05
On Subgraph Complementation to ,-free Graphs,duced by . in . results in a graph in .. We investigate the complexity of the problem when . is .-free for . being a complete graph, a star, a path, or a cycle. We obtain the following results:.Further, we prove that these hard problems do not admit subexponential-time algorithms (algorithms running
难取悦
发表于 2025-3-24 08:19:33
http://reply.papertrans.cn/39/3881/388038/388038_16.png
ANA
发表于 2025-3-24 14:46:02
Preventing Small ,-Cuts by Protecting Edges,of total cost at most . such that . has no (., .)-edge cut of capacity at most . that is disjoint from .. We show that . (., .). is NP-hard even on subcubcic graphs when all edges have capacity and cost one and provide a comprehensive study of the parameterized complexity of the problem. We show, fo
合群
发表于 2025-3-24 16:22:55
http://reply.papertrans.cn/39/3881/388038/388038_18.png
Ancestor
发表于 2025-3-24 21:36:22
http://reply.papertrans.cn/39/3881/388038/388038_19.png
充满装饰
发表于 2025-3-25 00:01:11
The Perfect Matching Cut Problem Revisited,ching cut, and is known to be .-complete. We revisit the problem and show that . remains .-complete when restricted to bipartite graphs of maximum degree 3 and arbitrarily large girth. Complementing this hardness result, we give two graph classes in which . is polynomial time solvable. The first one