Academic literature on the topic 'Pebbling'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Pebbling.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Pebbling"
Ye, Yongsheng, Fang Liu, and Caixia Shi. "The 2-Pebbling Property of the Middle Graph of Fan Graphs." Journal of Applied Mathematics 2014 (2014): 1–5. http://dx.doi.org/10.1155/2014/304514.
Full textBunde, David P., Erin W. Chambers, Daniel Cranston, Kevin Milans, and Douglas B. West. "Pebbling and optimal pebbling in graphs." Journal of Graph Theory 57, no. 3 (2008): 215–38. http://dx.doi.org/10.1002/jgt.20278.
Full textLi, Yueqing, and Yongsheng Ye. "The 2-pebbling property of squares of paths and Graham’s conjecture." Open Mathematics 18, no. 1 (March 10, 2020): 87–92. http://dx.doi.org/10.1515/math-2020-0009.
Full textMoews, David. "Pebbling graphs." Journal of Combinatorial Theory, Series B 55, no. 2 (July 1992): 244–52. http://dx.doi.org/10.1016/0095-8956(92)90043-w.
Full textLourdusamy, A., and T. Mathivanan. "Herscovici’s conjecture on C2n × G." Discrete Mathematics, Algorithms and Applications 12, no. 05 (July 1, 2020): 2050071. http://dx.doi.org/10.1142/s1793830920500718.
Full textCusack, Charles A., Airat Bekmetjev, and Mark Powers. "Two-pebbling and odd-two-pebbling are not equivalent." Discrete Mathematics 342, no. 3 (March 2019): 777–83. http://dx.doi.org/10.1016/j.disc.2018.10.030.
Full textGao, Ze-Tu, and Jian-Hua Yin. "The optimal pebbling of spindle graphs." Open Mathematics 17, no. 1 (November 13, 2019): 582–87. http://dx.doi.org/10.1515/math-2019-0094.
Full textChung, Fan, Ron Graham, John Morrison, and Andrew Odlyzko. "Pebbling a Chessboard." American Mathematical Monthly 102, no. 2 (February 1995): 113. http://dx.doi.org/10.2307/2975345.
Full textChung, Fan, Ron Graham, John Morrison, and Andrew Odlyzko. "Pebbling a Chessboard." American Mathematical Monthly 102, no. 2 (February 1995): 113–23. http://dx.doi.org/10.1080/00029890.1995.11990546.
Full textKirousis, Lefteris M., and Christos H. Papadimitriou. "Searching and pebbling." Theoretical Computer Science 47 (1986): 205–18. http://dx.doi.org/10.1016/0304-3975(86)90146-5.
Full textDissertations / Theses on the topic "Pebbling"
Yerger, Carl. "Extensions of Graph Pebbling." Scholarship @ Claremont, 2005. https://scholarship.claremont.edu/hmc_theses/176.
Full textBounadi, Monir. "The Foundations of Graph Pebbling." Thesis, Stockholms universitet, Matematiska institutionen, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-128482.
Full textMin handledare, Cecilia Holmgren, var tidigare anställd vid Matematiska institutionen, Stockholms universitet, men arbetar numera vid Matematiska institutionen, Uppsala universitet.
Nyberg, Brodda Carl-Fredrik. "Deterministic and Random Pebbling of Graphs." Thesis, Uppsala universitet, Analys och sannolikhetsteori, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-325833.
Full textMurphy, Kyle. "On t-Restricted Optimal Rubbling of Graphs." Digital Commons @ East Tennessee State University, 2017. https://dc.etsu.edu/etd/3251.
Full textNordström, Jakob. "Short Proofs May Be Spacious : Understanding Space in Resolution." Doctoral thesis, KTH, Teoretisk datalogi, TCS, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-4704.
Full textMost state-of-the-art satisfiability algorithms today are variants of the DPLL procedure augmented with clause learning. The two main bottlenecks for such algorithms are the amounts of time and memory used. Thus, understanding time and memory requirements for clause learning algorithms, and how these requirements are related to one another, is a question of considerable practical importance. In the field of proof complexity, these resources correspond to the length and space of resolution proofs for formulas in conjunctive normal form (CNF). There has been a long line of research investigating these proof complexity measures and relating them to the width of proofs, another measure which has turned out to be intimately connected with both length and space. Formally, the length of a resolution proof is the number of lines, i.e., clauses, the width of a proof is the maximal size of any clause in it, and the space is the maximal number of clauses kept in memory simultaneously if the proof is only allowed to infer new clauses from clauses currently in memory. While strong results have been established for length and width, our understanding of space has been quite poor. For instance, the space required to prove a formula is known to be at least as large as the needed width, but it has remained open whether space can be separated from width or whether the two measures coincide asymptotically. It has also been unknown whether the fact that a formula is provable in short length implies that it is also provable in small space (which is the case for length versus width), or whether on the contrary these measures are "completely unrelated" in the sense that short proofs can be maximally complex with respect to space. In this thesis, as an easy first observation we present a simplified proof of the recent length-space trade-off result for resolution in (Hertel and Pitassi 2007) and show how our ideas can be used to prove a couple of other exponential trade-offs in resolution. Next, we prove that there are families of CNF formulas that can be proven in linear length and constant width but require space growing logarithmically in the formula size, later improving this exponentially to the square root of the size. These results thus separate space and width. Using a related but different approach, we then resolve the question about the relation between space and length by proving an optimal separation between them. More precisely, we show that there are families of CNF formulas of size O(n) that have resolution proofs of length O(n) and width O(1) but for which any proof requires space Omega(n/log n). All of these results are achieved by studying so-called pebbling formulas defined in terms of pebble games over directed acyclic graphs (DAGs) and proving lower bounds on the space requirements for such formulas in terms of the black-white pebbling price of the underlying DAGs. Finally, we observe that our optimal separation of space and length is in fact a special case of a more general phenomenon. Namely, for any CNF formula F and any Boolean function f:{0,1}^d->{0,1}, replace every variable x in F by f(x_1, ..., x_d) and rewrite this new formula in CNF in the natural way, denoting the resulting formula F[f]. Then if F and f have the right properties, F[f] can be proven in resolution in essentially the same length and width as F but the minimal space needed for F[f] is lower-bounded by the number of variables that have to be mentioned simultaneously in any proof for F.
QC 20100831
Chiang, Hung-Hsing, and 姜宏興. "Optimally t-Pebbling Graphs." Thesis, 2018. http://ndltd.ncl.edu.tw/handle/3tnr33.
Full text中原大學
應用數學研究所
106
Let $G$ be a simple graph. A distribution $delta$ of $G$ is a mapping from $V(G)$ into the set of non-negative integers, where $delta(v)$ is the number of pebbles distributed to the vertex $v$ for each $vin V(G)$. A {it pebbling move} consists of removing two pebbles from one vertex and then placing one pebble at an adjacent vertex. A distribution of a given graph $G$ is $t$-fold solvable if, whenever we choose any target vertex $v$ of $G$, we can move $t$ pebbles on $v$ by using pebbling moves. The optimal $t$-pebbling number of the graph $G$, denoted by $pi^*_{t}(G)$, is the minimum number of pebbles necessary so that there is a $t$-fold solvable distribution of $G$. When $t=1$, the optimal $t$-pebbling number is the optimal pebbling number. In this thesis, we mainly study the optimal $t$-pebbling number of a graph. In Chapter $1$, we introduce the background of this study and give some basic definitions. For completeness, we also introduce the known results on the optimal pebbling number and the optimal $t$-pebbling number of a graph in Chapter $2$. In Chapter $3$, we study the optimal $t$-pebbling number of the cycle. As a consequence, we determine the exact value of $pi^*_{2}(C_{n})$ for each cycle $C_n$. We then derive an upper bound and a lower bound for $pi^*_{t}(C_{n})$ for $tgeq 3$. In Chapter $4$, let $T^m_h$ denote the complete $m$-ary tree with height $h$, we first show that $$pi^{ast}_{2}(T^2_{h})=pi^{ast}(T^2_{h+1})qquad ext{and} qquad pi^{ast}_{4}(T^2_{h})=pi^{ast}(T^2_{h+2})$$ and then determine the exact value of $pi^{ast}_{3}(T^2_{h})$. In Chapter $5$, we conclude our research results in this thesis.
Tsai, Tzung-Han, and 蔡宗翰. "Critical Pebbling Numbers of Graphs." Thesis, 2006. http://ndltd.ncl.edu.tw/handle/78244719347004481682.
Full text國立交通大學
應用數學系所
94
Given a distribution of pebbles on the vertices of a graph G, a pebbling step (or pebbling move) takes two pebbles from one vertex and place one pebble on an adjacent vertex. A distribution D of pebbles on the graph G is called solvable if, starting from D, it is possible to place a pebble on any given vertex using a sequence of pebbling steps. The pebbling number f(G) of a connected graph is the smallest number of pebbles such that every distribution with f(G) pebbles on G is solvable. A distribution D is r-solvable if there exists a sequence of pebbling steps which begin from D and end in at least one pebble on the vertex r. The r-critical pebbling number cr(G) is the largest size of a minimally r-solvable rooted distribution on G for any r. In this thesis, we first derive several known results from the study of pebbling numbers, and then we also obtain several new results on critical pebbling numbers. The results are (1) cr(Cm) = f(Cm)-1 if m_3 (mod 4), and f(Cm) otherwise; (2) cr(T) = 2d, where T is a tree and d is the diameter of T; (3) cr(P) = 6, where P is the Petersen graph; (4) cr(Qn) = 2n, where Qn is an n-cube; and (5) cr(C5¤C5) = 25.
Hertel, Philipp. "Clause Learning, Resolution Space, and Pebbling." Thesis, 2008. http://hdl.handle.net/1807/16736.
Full textChen, Ying-Zhen, and 陳盈臻. "Optimal pebbling of Cartesian product of Graphs." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/73288408397953881699.
Full text國立東華大學
應用數學系
104
Given a graph G, a distribution of pebbles on the vertices of G is a function D:V(G)→ℕ∪{0}. A basic pebbling move from a vertex v to a neighbor u takes away two pebbles at v and adds one pebble at u. Before the move, v must have at least two pebbles. A pebbling type α of G is a mapping from V(G) into ℕ∪{0}. A distribution D of pebbles of G is said to be an α-pebbling distribution if whenever we choose a target vertex v in G, we can move α(v) pebbles to v by applying pebbling moves successively(if necessary). In this case, we say that the vertex v is α(v)-solvable under D. For a given positive integer t, a t-pebbling distribution of G is an α-pebbling distribution of G with α(v)=t for any v∈V(G). The optimal α-pebbling number π_{α}^{∗}(G) is the minimum number of pebbles required in an α-pebbling distribution of G. If α is a t-pebbling distribution of G, we use π_{t}^{∗}(G) to replace π_{α}^{∗}(G) and call π_{t}^{∗}(G) the optimal t-pebbling number of G. And when t=1, we use π^{∗}(G) to replace π₁^{∗}(G) for simplicity. We study the optimal pebbling number and optimal 2-pebbling number of grids in this thesis. We give some basic properties for the optimal t-pebbling number of graphs in Section 2, and give the exact value of the optimal 2-pebbling number of P₂×P_{n} in Section 3. And, in Section 4, we give an upper bound for the optimal pebbling number of P_{m}×P_{n} for all n≥m≥6.
吳柏翰. "A Study on the Optimal Pebbling of Graphs." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/63762129550384143981.
Full textBooks on the topic "Pebbling"
Pebbling the walk: Surviving cancer caregiving. Portland, Or: Blue Heron Publishing, 2000.
Find full textBook chapters on the topic "Pebbling"
Galesi, Nicola, and Neil Thapen. "Resolution and Pebbling Games." In Theory and Applications of Satisfiability Testing, 76–90. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11499107_6.
Full textDwork, Cynthia, Moni Naor, and Hoeteck Wee. "Pebbling and Proofs of Work." In Advances in Cryptology – CRYPTO 2005, 37–54. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11535218_3.
Full textMatias, Yossi, and Ely Porat. "Efficient Pebbling for List Traversal Synopses." In Automata, Languages and Programming, 918–28. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/3-540-45061-0_71.
Full textKrál’ovič, Richard. "Time and Space Complexity of Reversible Pebbling." In SOFSEM 2001: Theory and Practice of Informatics, 292–303. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/3-540-45627-9_26.
Full textRužička, Peter, and Juraj Waczulík. "On time-space trade-offs in dynamic graph pebbling." In Lecture Notes in Computer Science, 671–81. Berlin, Heidelberg: Springer Berlin Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-57182-5_58.
Full textBlocki, Jeremiah, and Samson Zhou. "On the Depth-Robustness and Cumulative Pebbling Cost of Argon2i." In Theory of Cryptography, 445–65. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-70500-2_15.
Full textBlocki, Jeremiah, and Samson Zhou. "On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling." In Financial Cryptography and Data Security, 329–46. Berlin, Heidelberg: Springer Berlin Heidelberg, 2018. http://dx.doi.org/10.1007/978-3-662-58387-6_18.
Full textRanjan, Desh, John Savage, and Mohammad Zubair. "Upper and Lower I/O Bounds for Pebbling r-Pyramids." In Lecture Notes in Computer Science, 107–20. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-19222-7_12.
Full textAustrin, Per, Toniann Pitassi, and Yu Wu. "Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems." In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13–24. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-32512-0_2.
Full textKenter, Franklin, and Daphne Skipper. "Integer-Programming Bounds on Pebbling Numbers of Cartesian-Product Graphs." In Combinatorial Optimization and Applications, 681–95. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-030-04651-4_46.
Full textConference papers on the topic "Pebbling"
Kwasniewski, Grzegorz, Marko Kabić, Maciej Besta, Joost VandeVondele, Raffaele Solcà, and Torsten Hoefler. "Red-blue pebbling revisited." In SC '19: The International Conference for High Performance Computing, Networking, Storage, and Analysis. New York, NY, USA: ACM, 2019. http://dx.doi.org/10.1145/3295500.3356181.
Full textAbramsky, Samson, Anuj Dawar, and Pengming Wang. "The pebbling comonad in Finite Model Theory." In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE, 2017. http://dx.doi.org/10.1109/lics.2017.8005129.
Full textMeuli, Giulia, Mathias Soeken, Martin Roetteler, Nikolaj Bjorner, and Giovanni De Micheli. "Reversible Pebbling Game for Quantum Memory Management." In 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2019. http://dx.doi.org/10.23919/date.2019.8715092.
Full textNordström, Jakob. "On the Relative Strength of Pebbling and Resolution." In 2010 IEEE 25th Annual Conference on Computational Complexity (CCC). IEEE, 2010. http://dx.doi.org/10.1109/ccc.2010.22.
Full textHertel, Philipp, and Toniann Pitassi. "Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling." In 2007 48th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2007. http://dx.doi.org/10.1109/focs.2007.22.
Full textHertel, Philipp, and Toniann Pitassi. "Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling." In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07). IEEE, 2007. http://dx.doi.org/10.1109/focs.2007.4389487.
Full text