菊花
发表于 2025-3-30 11:31:09
The Power of Cut-Based Parameters for Computing Edge Disjoint Paths,hether . contains a set of pairwise edge-disjoint paths connecting every terminal pair in .. Our aim is to identify structural properties (parameters) of graphs which allow the efficient solution of EDP without restricting the placement of terminals in . in any way. In this setting, EDP is known to
quiet-sleep
发表于 2025-3-30 16:13:56
http://reply.papertrans.cn/39/3881/388039/388039_52.png
Bronchial-Tubes
发表于 2025-3-30 16:56:37
http://reply.papertrans.cn/39/3881/388039/388039_53.png
decipher
发表于 2025-3-30 22:31:10
,Classified Rank-Maximal Matchings and Popular Matchings – Algorithms and Hardness,hbors in ., possibly involving ties, and each vertex can have capacities and classifications. A classification . for a vertex . is a collection of subsets of neighbors of .. Each subset (class) . has an . denoting the maximum number of vertices from . that can be matched to .. The goal is to find a
牵连
发表于 2025-3-31 03:09:55
https://doi.org/10.1385/1592599281orphism, defined analogously, the situation seems more complicated. We show the dichotomy theorem for simple connected graphs . with maximum degree 2. If . is isomorphic to . or ., then the existence of a locally surjective homomorphism from a string graph with . vertices to . can be decided in time
尖
发表于 2025-3-31 07:20:40
Molecular Diagnostics in Cancer Patientsis result by showing that the problem remains tractable on .-free graphs, for any fixed .. Along the way, we show that subcubic . is tractable for graphs excluding a type of graph we call an “apple with a long stem”, generalizing known results for apple-free graphs.
CLIFF
发表于 2025-3-31 11:56:05
Molecular Diagnostics of Cancern several ways, and in particular no deterministic algorithm with approximation ratio . (with .) can run in a constant number of rounds. We also prove results of a similar flavour for the . problem in regular oriented graphs, where we want to maximize the number of arcs oriented from the left part t
痛苦一下
发表于 2025-3-31 15:54:26
http://reply.papertrans.cn/39/3881/388039/388039_58.png
GIST
发表于 2025-3-31 17:30:55
Molecular Ecology of Aquatic Communities on every graph class of bounded treecut width. Our second result shows that EDP parameterized by treecut width is unlikely to be fixed-parameter tractable. Our final, third result is a polynomial kernel for EDP parameterized by the size of a minimum feedback edge set in the graph.
神圣将军
发表于 2025-3-31 21:45:09
https://doi.org/10.1007/978-1-4615-7482-8ve instances, even when the input graph is composed of a maximal planar graph, namely a double-wheel graph, and an edge. We conjecture that planar graphs always admit a (not necessarily planar) realization in the dichotomous setting.