全文获取类型
收费全文 | 100篇 |
免费 | 17篇 |
国内免费 | 3篇 |
专业分类
化学 | 1篇 |
综合类 | 3篇 |
数学 | 116篇 |
出版年
2024年 | 1篇 |
2023年 | 2篇 |
2022年 | 3篇 |
2021年 | 1篇 |
2020年 | 4篇 |
2019年 | 6篇 |
2018年 | 8篇 |
2017年 | 8篇 |
2016年 | 6篇 |
2015年 | 2篇 |
2014年 | 2篇 |
2013年 | 3篇 |
2012年 | 3篇 |
2011年 | 4篇 |
2010年 | 11篇 |
2009年 | 9篇 |
2008年 | 3篇 |
2007年 | 4篇 |
2006年 | 9篇 |
2005年 | 4篇 |
2004年 | 4篇 |
2003年 | 5篇 |
2002年 | 3篇 |
2001年 | 2篇 |
2000年 | 3篇 |
1999年 | 1篇 |
1998年 | 3篇 |
1997年 | 1篇 |
1996年 | 1篇 |
1995年 | 1篇 |
1994年 | 1篇 |
1993年 | 1篇 |
1986年 | 1篇 |
排序方式: 共有120条查询结果,搜索用时 15 毫秒
1.
The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s1,…,sk,t1,…,tk, the graph contains k vertex disjoint paths joining sr to tr for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007 相似文献
2.
We discuss the length of the longest directed cycle in the sparse random digraph , constant. We show that for large there exists a function such that a.s. The function where is a polynomial in . We are only able to explicitly give the values , although we could in principle compute any . 相似文献
3.
We prove part of a conjecture by Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28.) regarding threshold functions for the existence of an H‐factor in a random graph . We prove that the conjectured threshold function is correct for any graph H which is not covered by its densest subgraphs. We also demonstrate that the main result of Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28) generalizes to multigraphs, digraphs, and a multipartite model. 相似文献
4.
Sufficient Conditions for Maximally Edge-connected and Super-edge-connected Digraphs Depending on the Size 下载免费PDF全文
Let D be a finite and simple digraph with vertex set V (D). The minimum degree δ of a digraph D is defined as the minimum value of its out-degrees and its in-degrees. If D is a digraph with minimum degree δ and edge-connectivity λ, then λ ≤ δ. A digraph is maximally edge-connected if λ=δ. A digraph is called super-edge-connected if every minimum edge-cut consists of edges incident to or from a vertex of minimum degree. In this note we show that a digraph is maximally edge-connected or super-edge-connected if the number of arcs is large enough. 相似文献
5.
It is well known that Moore digraphs do not exist except for trivial cases (degree 1 or diameter 1), but there are digraphs of diameter two and arbitrary degree which miss the Moore bound by one. No examples of such digraphs of diameter at least three are known, although several necessary conditions for their existence have been obtained. In this paper, we prove that digraphs of degree three and diameter k ≥ 3 which miss the Moore bound by one do not exist. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 112–126, 2005 相似文献
6.
Ma?gorzata Zwonek 《Discrete Mathematics》2006,306(18):2282-2291
In the paper two different arc-colourings and two associated with the total colourings of digraphs are considered. In one of these colourings we show that the problem of calculating the total chromatic index reduces to that of calculating the chromatic number of the underlying graph. In the other colouring we find the total chromatic indices of complete symmetric digraphs and tournaments. 相似文献
7.
Analterable digraph is a digraph with a subset of its edges marked alterable and their orientations left undecided. We say that an alterable digraph has an invariant ofk on the length of the longest circuit if it has a circuit of length at leastk regardless of the orientations over its alterable edges. Computing the maximum invariant on the length of the longest circuit in an alterable digraph is aglobal optimization problem. We show that it is hard to approximate the global optimal solution for the maximum invariant problem.Research supported in part by NSF grant CCR 9121472. 相似文献
8.
An n‐state deterministic finite automaton over a k‐letter alphabet can be seen as a digraph with n vertices which all have k labeled out‐arcs. Grusho (Publ Math Inst Hungarian Acad Sci 5 (1960), 17–61). proved that whp in a random k‐out digraph there is a strongly connected component of linear size, i.e., a giant, and derived a central limit theorem. We show that whp the part outside the giant contains at most a few short cycles and mostly consists of tree‐like structures, and present a new proof of Grusho's theorem. Among other things, we pinpoint the phase transition for strong connectivity. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 428–458, 2017 相似文献
9.
10.
Jørgen Bang‐Jensen Tilde My Christiansen Alessandro Maddaloni 《Journal of Graph Theory》2017,85(2):545-567
The k‐linkage problem is as follows: given a digraph and a collection of k terminal pairs such that all these vertices are distinct; decide whether D has a collection of vertex disjoint paths such that is from to for . A digraph is k‐linked if it has a k‐linkage for every choice of 2k distinct vertices and every choice of k pairs as above. The k‐linkage problem is NP‐complete already for [11] and there exists no function such that every ‐strong digraph has a k‐linkage for every choice of 2k distinct vertices of D [17]. Recently, Chudnovsky et al. [9] gave a polynomial algorithm for the k‐linkage problem for any fixed k in (a generalization of) semicomplete multipartite digraphs. In this article, we use their result as well as the classical polynomial algorithm for the case of acyclic digraphs by Fortune et al. [11] to develop polynomial algorithms for the k‐linkage problem in locally semicomplete digraphs and several classes of decomposable digraphs, including quasi‐transitive digraphs and directed cographs. We also prove that the necessary condition of being ‐strong is also sufficient for round‐decomposable digraphs to be k‐linked, obtaining thus a best possible bound that improves a previous one of . Finally we settle a conjecture from [3] by proving that every 5‐strong locally semicomplete digraph is 2‐linked. This bound is also best possible (already for tournaments) [1]. 相似文献