Зміст
Добірка наукової літератури з теми "Discrete Mathematics, Computing Science, Graph Theory, Temporal Graphs"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся зі списками актуальних статей, книг, дисертацій, тез та інших наукових джерел на тему "Discrete Mathematics, Computing Science, Graph Theory, Temporal Graphs".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Статті в журналах з теми "Discrete Mathematics, Computing Science, Graph Theory, Temporal Graphs"
1
Crescenzi, Pierluigi, Clémence Magnien, and Andrea Marino. "Finding Top-k Nodes for Temporal Closeness in Large Temporal Graphs." Algorithms 13, no. 9 (August 29, 2020): 211. http://dx.doi.org/10.3390/a13090211.
Повний текст джерелаАнотація:
The harmonic closeness centrality measure associates, to each node of a graph, the average of the inverse of its distances from all the other nodes (by assuming that unreachable nodes are at infinite distance). This notion has been adapted to temporal graphs (that is, graphs in which edges can appear and disappear during time) and in this paper we address the question of finding the top-k nodes for this metric. Computing the temporal closeness for one node can be done in O(m) time, where m is the number of temporal edges. Therefore computing exactly the closeness for all nodes, in order to find the ones with top closeness, would require O(nm) time, where n is the number of nodes. This time complexity is intractable for large temporal graphs. Instead, we show how this measure can be efficiently approximated by using a “backward” temporal breadth-first search algorithm and a classical sampling technique. Our experimental results show that the approximation is excellent for nodes with high closeness, allowing us to detect them in practice in a fraction of the time needed for computing the exact closeness of all nodes. We validate our approach with an extensive set of experiments.
2
Lobov, Alexander A., and Mikhail B. Abrosimov. "About uniqueness of the minimal 1-edge extension of hypercube Q4." Prikladnaya Diskretnaya Matematika, no. 58 (2023): 84–93. http://dx.doi.org/10.17223/20710410/58/8.
Повний текст джерелаАнотація:
One of the important properties of reliable computing systems is their fault tolerance. To study fault tolerance, you can use the apparatus of graph theory. Minimal edge extensions of a graph are considered, which are a model for studying the failure of links in a computing system. A graph G* = (V*,α*) with n vertices is called a minimal k-edge extension of an n-vertex graph G = (V, α) if the graph G is embedded in every graph obtained from G* by deleting any of its k edges and has the minimum possible number of edges. The hypercube Qn is a regular 2n-vertex graph of order n, which is the Cartesian product of n complete 2-vertex graphs K2. The hypercube is a common topology for building computing systems. Previously, a family of graphs Q*n was described, whose representatives for n>1 are minimal edge 1-extensions of the corresponding hypercubes. In this paper, we obtain an analytical proof of the uniqueness of minimal edge 1-extensions of hypercubes for n≤4 and establish a general property of an arbitrary minimal edge 1-extension of a hypercube Qn for n>2: it does not contain edges connecting vertices, the distance between which in the hypercube is equal to 2.
3
Almerich-Chulia, Ana, Abel Cabrera Martínez, Frank Angel Hernández Mira, and Pedro Martin-Concepcion. "From Total Roman Domination in Lexicographic Product Graphs to Strongly Total Roman Domination in Graphs." Symmetry 13, no. 7 (July 16, 2021): 1282. http://dx.doi.org/10.3390/sym13071282.
Повний текст джерелаАнотація:
Let G be a graph with no isolated vertex and let N(v) be the open neighbourhood of v∈V(G). Let f:V(G)→{0,1,2} be a function and Vi={v∈V(G):f(v)=i} for every i∈{0,1,2}. We say that f is a strongly total Roman dominating function on G if the subgraph induced by V1∪V2 has no isolated vertex and N(v)∩V2≠∅ for every v∈V(G)\V2. The strongly total Roman domination number of G, denoted by γtRs(G), is defined as the minimum weight ω(f)=∑x∈V(G)f(x) among all strongly total Roman dominating functions f on G. This paper is devoted to the study of the strongly total Roman domination number of a graph and it is a contribution to the Special Issue “Theoretical Computer Science and Discrete Mathematics” of Symmetry. In particular, we show that the theory of strongly total Roman domination is an appropriate framework for investigating the total Roman domination number of lexicographic product graphs. We also obtain tight bounds on this parameter and provide closed formulas for some product graphs. Finally and as a consequence of the study, we prove that the problem of computing γtRs(G) is NP-hard.
4
WU, XIAODONG, DANNY Z. CHEN, KANG LI, and MILAN SONKA. "THE LAYERED NET SURFACE PROBLEMS IN DISCRETE GEOMETRY AND MEDICAL IMAGE SEGMENTATION." International Journal of Computational Geometry & Applications 17, no. 03 (June 2007): 261–96. http://dx.doi.org/10.1142/s0218195907002331.
Повний текст джерелаАнотація:
Efficient detection of multiple inter-related surfaces representing the boundaries of objects of interest in d-D images (d ≥ 3) is important and remains challenging in many medical image analysis applications. In this paper, we study several layered net surface (LNS) problems captured by an interesting type of geometric graphs called ordered multi-column graphs in the d-D discrete space (d ≥ 3 is any constant integer). The LNS problems model the simultaneous detection of multiple mutually related surfaces in three or higher dimensional medical images. Although we prove that the d-D LNS problem (d ≥ 3) on a general ordered multi-column graph is NP-hard, the (special) ordered multi-column graphs that model medical image segmentation have the self-closure structures and thus admit polynomial time exact algorithms for solving the LNS problems. Our techniques also solve the related net surface volume (NSV) problems of computing well-shaped geometric regions of an optimal total volume in a d-D weighted voxel grid. The NSV problems find applications in medical image segmentation and data mining. Our techniques yield the first polynomial time exact algorithms for several high dimensional medical image segmentation problems. Experiments and comparisons based on real medical data showed that our LNS algorithms and software are computationally efficient and produce highly accurate and consistent segmentation results.
5
Thomas, Colin, Maximilien Cosme, Cédric Gaucherel, and Franck Pommereau. "Model-checking ecological state-transition graphs." PLOS Computational Biology 18, no. 6 (June 6, 2022): e1009657. http://dx.doi.org/10.1371/journal.pcbi.1009657.
Повний текст джерелаАнотація:
Model-checking is a methodology developed in computer science to automatically assess the dynamics of discrete systems, by checking if a system modelled as a state-transition graph satisfies a dynamical property written as a temporal logic formula. The dynamics of ecosystems have been drawn as state-transition graphs for more than a century, ranging from state-and-transition models to assembly graphs. Model-checking can provide insights into both empirical data and theoretical models, as long as they sum up into state-transition graphs. While model-checking proved to be a valuable tool in systems biology, it remains largely underused in ecology apart from precursory applications. This article proposes to address this situation, through an inventory of existing ecological STGs and an accessible presentation of the model-checking methodology. This overview is illustrated by the application of model-checking to assess the dynamics of a vegetation pathways model. We select management scenarios by model-checking Computation Tree Logic formulas representing management goals and built from a proposed catalogue of patterns. In discussion, we sketch bridges between existing studies in ecology and available model-checking frameworks. In addition to the automated analysis of ecological state-transition graphs, we believe that defining ecological concepts with temporal logics could help clarify and compare them.
6
Blum, Johannes, Stefan Funke, and Sabine Storandt. "Sublinear search spaces for shortest path planning in grid and road networks." Journal of Combinatorial Optimization 42, no. 2 (July 29, 2021): 231–57. http://dx.doi.org/10.1007/s10878-021-00777-3.
Повний текст джерелаАнотація:
AbstractShortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths in, e.g., road or grid networks is an important challenge. The most successful techniques for fast query answering rely on preprocessing. However, for many of these techniques it is not fully understood why they perform so remarkably well, and theoretical justification for the empirical results is missing. An attempt to explain the excellent practical performance of preprocessing based techniques on road networks (as transit nodes, hub labels, or contraction hierarchies) in a sound theoretical way are parametrized analyses, e.g., considering the highway dimension or skeleton dimension of a graph. Still, these parameters may be large in case the network contains grid-like substructures—which inarguably is the case for real-world road networks around the globe. In this paper, we use the very intuitive notion of bounded growth graphs to describe road networks and also grid graphs. We show that this model suffices to prove sublinear search spaces for the three above mentioned state-of-the-art shortest path planning techniques. Furthermore, our preprocessing methods are close to the ones used in practice and only require expected polynomial time.
7
Gurski, Frank, Dominique Komander, Carolin Rehs, Jochen Rethmann, and Egon Wanke. "Computing directed Steiner path covers." Journal of Combinatorial Optimization, July 27, 2021. http://dx.doi.org/10.1007/s10878-021-00781-7.
Повний текст джерелаАнотація:
AbstractIn this article we consider the Directed Steiner Path Cover problem on directed co-graphs. Given a directed graph $$G=(V,E)$$ G = ( V , E ) and a set $$T \subseteq V$$ T ⊆ V of so-called terminal vertices, the problem is to find a minimum number of vertex-disjoint simple directed paths, which contain all terminal vertices and a minimum number of non-terminal vertices (Steiner vertices). The primary minimization criteria is the number of paths. We show how to compute in linear time a minimum Steiner path cover for directed co-graphs. This leads to a linear time computation of an optimal directed Steiner path on directed co-graphs, if it exists. Since the Steiner path problem generalizes the Hamiltonian path problem, our results imply the first linear time algorithm for the directed Hamiltonian path problem on directed co-graphs. We also give binary integer programs for the (directed) Hamiltonian path problem, for the (directed) Steiner path problem, and for the (directed) Steiner path cover problem. These integer programs can be used to minimize change-over times in pick-and-place machines used by companies in electronic industry.
8
Garijo, Delia, Antonio González, and Alberto Márquez. "The resolving number of a graph Delia." Discrete Mathematics & Theoretical Computer Science Vol. 15 no. 3, Graph Theory (December 10, 2013). http://dx.doi.org/10.46298/dmtcs.615.
Повний текст джерелаАнотація:
Graph Theory International audience We study a graph parameter related to resolving sets and metric dimension, namely the resolving number, introduced by Chartrand, Poisson and Zhang. First, we establish an important difference between the two parameters: while computing the metric dimension of an arbitrary graph is known to be NP-hard, we show that the resolving number can be computed in polynomial time. We then relate the resolving number to classical graph parameters: diameter, girth, clique number, order and maximum degree. With these relations in hand, we characterize the graphs with resolving number 3 extending other studies that provide characterizations for smaller resolving number.
9
Merino, Criel. "The Number of Quasi-Trees in Fans and Wheels." Electronic Journal of Combinatorics 30, no. 1 (March 10, 2023). http://dx.doi.org/10.37236/11097.
Повний текст джерелаАнотація:
We extend the classical relation between the $2n$-th Fibonacci number and the number of spanning trees of the $n$-fan graph to ribbon graphs. More importantly, we establish a relation between the $n$-associated Mersenne number and the number of quasi trees of the $n$-wheel ribbon graph. The calculations are performed by computing the determinant of a matrix associated with ribbon graphs. These theorems are also proven using contraction and deletion in ribbon graphs. The results provide neat and symmetric combinatorial interpretations of these well-known sequences. Furthermore, they are refined by giving two families of abelian groups whose orders are the Fibonacci and associated Mersenne numbers.
10
Burger, Anton Pierre, Alewyn Petrus Villiers, and Jan Harm Vuuren. "Edge stability in secure graph domination." Discrete Mathematics & Theoretical Computer Science Vol. 17 no. 1, Graph Theory (March 16, 2015). http://dx.doi.org/10.46298/dmtcs.2120.
Повний текст джерелаАнотація:
Graph Theory International audience A subset X of the vertex set of a graph G is a secure dominating set of G if X is a dominating set of G and if, for each vertex u not in X, there is a neighbouring vertex v of u in X such that the swap set (X-v)∪u is again a dominating set of G. The secure domination number of G is the cardinality of a smallest secure dominating set of G. A graph G is p-stable if the largest arbitrary subset of edges whose removal from G does not increase the secure domination number of the resulting graph, has cardinality p. In this paper we study the problem of computing p-stable graphs for all admissible values of p and determine the exact values of p for which members of various infinite classes of graphs are p-stable. We also consider the problem of determining analytically the largest value ωn of p for which a graph of order n can be p-stable. We conjecture that ωn=n-2 and motivate this conjecture.
Дисертації з теми "Discrete Mathematics, Computing Science, Graph Theory, Temporal Graphs"
1
Capresi, Chiara. "Algorithms for identifying clusters in temporal graphs and realising distance matrices by unicyclic graphs." Doctoral thesis, Università di Siena, 2022. http://hdl.handle.net/11365/1211314.
Повний текст джерелаАнотація:
In this thesis I present some results, which mainly concern finding algorithms for graphs problems, to which I worked on during my Ph.D with the supervision of my supervisors. In particular, as a first theme, it is presented a new temporal interpretation of the well studied \ClusterEditing which we called \EditTempClique (\ETC). In this regard, %at first it is shown that the corresponding versions in the temporal setting of any \NP-Hard version of \ClusterEditing is still \NP-Hard. Then,
in this work, it is proved that \ETC is \NP-Complete even if we restrict the possible inputs to the class of temporal graphs with a path as their underlying graph. Furthermore, it is presented a result that shows that \ETC is instead tractable in polynomial time if the underlying graph is a path and the maximum number of appearances allowed for each of the edges of that path is fixed.
Taking in mind the known key observation that a static graph is a cluster graph if and only if it does not contain any induced $P_3$, it is presented a local characterisation for cluster temporal graphs. This characterisation establishes that a temporal graph is a cluster temporal graph if and only if every subset of at most five vertices induces a cluster temporal graph. Using this characterisation, we obtain an \FPT~algorithm for \ETC parameterised simultaneously by the number of modifications and the lifetime (number of timesteps) of the input temporal graph. Furthermore, it is shown via a counterexample, that a cluster temporal graph can not be properly characterised by sets of at most four vertices.
In the last Chapter of this thesis, at first it is proven a result on the realisation of distance matrices by $n-$cycles and then it is developed an algorithm that allows to establish if a given distance matrix $D$ can or cannot be realised by a weighted unicyclic graph or at least by a weighted tree. In case of affirmative answer, a second part of the algorithm reconstructs that graph. The algorithm takes $\mathcal O(n^4)$. Furthermore, it is shown that if the algorithm returns a unicyclic graph as a realisation of $D$, then this realisation is optimal.