esthetician
发表于 2025-3-26 22:23:39
Cliques in Regular Graphs and the Core-Periphery Problem in Social Networks a regularization procedure that transforms a given graph with maximum degree . into a .-regular graph with the same clique number by adding at most . new nodes. This is of independent interest because it implies that finding a maximum clique in a regular graph is .-hard to approximate to within a factor of . for all ..
gratify
发表于 2025-3-27 02:17:15
Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problemving the result of Aurora et al. who presented an .-approximation for the weighted case..We also present a PTAS for .-minor free graphs, if the demands on the edges are bounded above by a constant, and we show that the problem is APX-hard even for cubic graphs and bounded degree bipartite graphs with ..
mortgage
发表于 2025-3-27 08:46:22
On the Complexity of Extracting Subtree with Keeping Distinguishabilityhether there is a small enough subtree . of ., such that for query class . and node sets . and ., . preserves the . of .. In this paper, as an initial attempt of investigating this problem, fixing . to be a specific part of . (introduced later), the subtree extraction problem is shown to be NP-..
Cytology
发表于 2025-3-27 09:44:56
http://reply.papertrans.cn/23/2300/229964/229964_34.png
pantomime
发表于 2025-3-27 16:23:21
Conclusion: Connecting the Dots, leads to simultaneous broadcasting of optimal number of messages on a wide class of graphs in optimal time. In particular, we provide tight results for bipartite tori, meshes, hypercubes. Several problems and conjectures are proposed.
爱花花儿愤怒
发表于 2025-3-27 17:56:18
http://reply.papertrans.cn/23/2300/229964/229964_36.png
GRAIN
发表于 2025-3-27 22:59:39
http://reply.papertrans.cn/23/2300/229964/229964_37.png
Amorous
发表于 2025-3-28 05:55:46
http://reply.papertrans.cn/23/2300/229964/229964_38.png
Facet-Joints
发表于 2025-3-28 08:36:03
An Introduction to Coding Sequences of Graphsinary matroids, we obtain a characterization for simple graphic matroids. Introducing concepts of segment binary matroid and strong isomorphisms we show that two simple undirected graphs are isomorphic if and only if their canonical sequences are strongly isomorphic simple segment binary matroids... 05C62, 05C50, 05B35.
配偶
发表于 2025-3-28 13:14:17
Approximation and Hardness Results for the Max ,-Uncut Problemroximation 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 ..