开始发作
发表于 2025-3-23 10:39:15
Embedding Problems for Paths with Direction Constrained Edgescts the directions assigned to its edges. This problem arises in the context of extending planar graph embedding techniques and VLSI rectilinear layout techniques from 2. to 3.. We give combinatorial characterizations of reachability that yield linear time recognition and layout algorithms.
BLANC
发表于 2025-3-23 16:10:29
Rectangular Drawings of Plane Graphs Without Designated Corners a necessary and sufficient condition for the existence of a rectangular drawing of . for the general case in which no vertices are designated as corners. We also give a linear-time algorithm to find a rectangular drawing of . if it exists.
vibrant
发表于 2025-3-23 19:01:05
Approximation Algorithms for Independent Sets in Map Graphsiven a weight, while a ratio of .(log .) can be achieved in .(.. log .) time otherwise. Behind the design of our algorithms are several fundamental results for map graphs; these results can be used to design good approximation algorithms for coloring and vertex cover in map graphs, and may find applications to other problems on map graphs as well.
惊惶
发表于 2025-3-24 00:22:56
Efficient Algorithms for the Minimum Connected Domination on Trapezoid Graphsifferent approach for finding the minimum cardinality connected dominating set in trapezoid graphs using . time. For finding the minimum weighted connected dominating set, we show the problem can be efficiently solved in .(. log log .) time.
diabetes
发表于 2025-3-24 04:42:06
Parameterized Complexity of Finding Subgraphs with Hereditary Propertiese parameterized class W and is fixed parameter tractable otherwise. In the former case, if the forbidden set of the property is finite, we show, in fact, that the problem is W-complete (see [.] for definitions). Our proofs, both of the tractability as well as the hardness ones, involve clever use of Ramsey numbers.
Malleable
发表于 2025-3-24 08:11:00
Closure Properties of Real Number Classes under Limits and Computable Operatorseakly computable real numbers is not closed under effective limit and partial computable functions while the class of recursively approximable real numbers is closed under effective limit and partial computable functions.
座右铭
发表于 2025-3-24 14:01:25
http://reply.papertrans.cn/24/2348/234778/234778_17.png
disciplined
发表于 2025-3-24 15:07:54
Hierarchical Topological Inference on Planar Disc Mapsvery (.) ∈⋈., and (3) . includes . as a sub-region for every (.) ∈⋈.. This problem arises from the study in geographic information systems. The problem is in NP but not known to be NP-hard or polynomial-time solvable. This paper shows that a nontrivial special case of the problem can be solved in almost linear time.
Perceive
发表于 2025-3-24 21:48:16
http://reply.papertrans.cn/24/2348/234778/234778_19.png
杂色
发表于 2025-3-25 02:38:42
http://reply.papertrans.cn/24/2348/234778/234778_20.png