LIEN
发表于 2025-3-28 15:17:46
Computing a Tree Having a Small Vertex Coverhard to achieve an .-approximation for the problem with general graphs. In this paper, we present constant-factor approximation algorithms for the problem with unit disk graphs and with graphs excluding a fixed minor.
停止偿付
发表于 2025-3-28 18:48:56
On the Approximability of ,ed fixed-cardinality maximization problem . that aims at maximizing the number of equivalence classes induced by a solution set of . vertices. We study the approximation complexity of . on general hypergraphs and on more restricted instances, in particular, neighborhood hypergraphs of graphs.
我不怕牺牲
发表于 2025-3-29 00:13:19
Finding Disjoint Paths on Edge-Colored Graphs: A Multivariate Complexity Analysishose goal is to find the maximum number of vertex-disjoint and color-disjoint uni-color paths. We extend some of the results of . to this new variant, and we prove that unlike ., . is already hard on graphs at distance two from disjoint paths.
Insulin
发表于 2025-3-29 06:14:47
Fast Searching on Complete ,-partite Graphsaphs, such as complete bipartite graphs and complete split graphs. We solve the open problem of determining the fast search number of complete bipartite graphs, and present upper and lower bounds on the fast search number of complete split graphs.
最低点
发表于 2025-3-29 07:42:20
http://reply.papertrans.cn/23/2300/229964/229964_45.png
变量
发表于 2025-3-29 12:01:09
http://reply.papertrans.cn/23/2300/229964/229964_46.png
Outmoded
发表于 2025-3-29 15:56:28
John Hunt BSc, PhD, MBCS, C.Engand present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity of the problem. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between tree-depth and vertex cover number.
厌倦吗你
发表于 2025-3-29 19:59:03
Safe Sets in Graphs: Graph Classes and Structural Parametersand present polynomial-time algorithms for graphs of bounded treewidth, and also for interval graphs. We also study the parameterized complexity of the problem. We show that the problem is fixed-parameter tractable when parameterized by the solution size. Furthermore, we show that this parameter lies between tree-depth and vertex cover number.
Exposure
发表于 2025-3-30 02:11:16
0302-9743selected from 122 submissions. The papers are organized in topical sections such as graph theory, geometric optimization, complexity and data structure, combinatorial optimization, and miscellaneous..978-3-319-48748-9978-3-319-48749-6Series ISSN 0302-9743 Series E-ISSN 1611-3349
JOT
发表于 2025-3-30 06:04:40
Smaller Satellites: Bigger Business?roximation algorithm, and an .-approximation algorithm by reducing it to ., where . is the approximation ratio for the . problem. More importantly, we show that . and . are in fact equivalent in approximability up to a factor of 2. We also prove a weak approximation hardness result for . under the assumption ..