可憎
发表于 2025-3-28 18:10:16
Cops and Robbers on 1-Planar Graphsat most one crossing per edge. In contrast to planar graphs, we show that some 1-planar graphs have unbounded cop number. Meanwhile, for maximal 1-planar graphs, we prove that three cops are always sufficient and sometimes necessary. In addition, we completely determine the cop number of outer 1-planar graphs.
mediocrity
发表于 2025-3-28 20:17:44
Fixed-Parameter Algorithms for Computing RAC Drawings of Graphs of RAC drawings from the viewpoint of parameterized complexity. In particular, we establish that computing a RAC drawing of an input graph . with at most . bends (or determining that none exists) is fixed-parameter tractable parameterized by either the feedback edge number of ., or . plus the vertex cover number of ..
Ascendancy
发表于 2025-3-29 00:01:48
http://reply.papertrans.cn/39/3880/387921/387921_43.png
bronchodilator
发表于 2025-3-29 04:15:26
Upward and Orthogonal Planarity are W-Hard Parameterized by Treewidthblems. We prove that the flow problem is W-hard parameterized by treewidth on planar graphs, and that the existing chain of reductions to the planarity testing problems can be adapted without blowing up the treewidth. Our reductions also show that the known .-time algorithms cannot be improved to run in time . unless . fails.
吹牛大王
发表于 2025-3-29 08:41:52
https://doi.org/10.1007/978-3-322-81174-5 showing that the problem remains fixed-parameter tractable when parameterized only by the number of vertices of degree at most two plus the number of bends. As a consequence, rectilinear planarity testing lies in . parameterized by the number of vertices of degree at most two.
Serenity
发表于 2025-3-29 12:46:00
https://doi.org/10.1007/978-3-658-29887-6le with respect to each of the following parameters: the vertex cover number, the segment number, and the line cover number. We also consider colored versions of the segment and the line cover number.
LAITY
发表于 2025-3-29 16:54:20
https://doi.org/10.1007/978-3-322-93701-8 on linear programming, (ii) a selection of simple algorithms that together produce competitive results, and (iii) an extensive experimental comparison of our pipeline with existing approaches using standard benchmark sets and metrics.
大炮
发表于 2025-3-29 20:50:20
https://doi.org/10.1007/978-3-658-13147-0terized by the branchwidth (and hence by the treewidth) of the graph; (ii) we establish that MBS parameterized by the number of non-bimodal vertices admits a polynomial kernel. As the byproduct of these results, we obtain a subexponential FPT algorithm and an efficient polynomial-time approximation scheme for MBS.
600
发表于 2025-3-30 02:14:40
http://reply.papertrans.cn/39/3880/387921/387921_49.png
FRAUD
发表于 2025-3-30 04:29:37
http://reply.papertrans.cn/39/3880/387921/387921_50.png