| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju


1 - 10 / 24
Na začetekNa prejšnjo stran123Na naslednjo stranNa konec
On edge connectivity of direct products of graphs
Xiang-Lan Cao, Špela Brglez, Simon Špacapan, Elkin Vumar, 2011, izvirni znanstveni članek

Opis: Let ▫$lambda(G)$▫ be the edge connectivity of ▫$G$▫. The direct product of graphs ▫$G$▫ and ▫$H$▫ is the graph with vertex set ▫$V(G times H) = V(G) times V(H)$▫, where two vertices ▫$(u_1,v_1)$▫ and ▫$(u_2,v_2)$▫ are adjacent in ▫$G times H$▫ if ▫$u_1u_2 in E(G)$▫ and ▫$v_1v_2 in E(H)$▫. We prove that ▫$lambda(G times K_n) = min{n(n-1)lambda(G), (n-1)delta(G)}$▫ for every nontrivial graph ▫$G$▫ and ▫$n geqslant 3$▫. We also prove that for almost every pair of graphs ▫$G$▫ and ▫$H$▫ with ▫$n$▫ vertices and edge probability ▫$p$▫, ▫$G times H$▫ is ▫$k$▫-connected, where ▫$k=O((n/log n)^2)$▫.
Ključne besede: mathematics, graph theory, combinatorial problems, connectivity, direct product, graph product, separating set
Objavljeno: 01.06.2012; Ogledov: 1456; Prenosov: 170
URL Povezava na celotno besedilo

Acceleration of sweep-line technique by employing smart quicksort
David Podgorelec, Gregor Klajnšek, 2005, izvirni znanstveni članek

Opis: Quicksort is usually the best practical choice for sorting because it is, on average, remarkably efficient. Unfortunately, this popular algorithm has a significant drawback: the slowest performance is obtained in the simplest cases when input data are already initially sorted or only a slight perturbation occurs. In this paper, we propose a combination of quicksort and a new algorithm, which shows excellent time performance in sorting such crucial data arrays, and which is not much slower than quicksort in random cases. Our work was inspired by problems met when sorting polygon vertices in the sweep-line algorithms of computational geometry and, therefore, we have named the new algorithm 'vertex sort'. It splits the input array into three sub-arrays. Two of them are already sorted, and the third one is handled iteratively. A simple test decides whether to continue recursively with vertexsort or to employ quicksort in the second iteration. In this way, we achieve a situation where the worst case time complexity does not exceed the running times of quicksort, but the simplest cases are handled much faster (inlinear time) than random cases. We have named the combined algorithm 'smartquicksort' because of this desired property. In the last part of the paper, we prove its efficiency by employing it in a well-known sweep-line-based polygon triangulation algorithm.
Ključne besede: computational geometry, quicksort, smart quicksort, sweep-line, smart quicksort, polygon triangualation, vertex sort
Objavljeno: 01.06.2012; Ogledov: 1197; Prenosov: 45
URL Povezava na celotno besedilo

Identification of critical points for the design and synthesis of flexible processes
Zorka Novak-Pintarič, Zdravko Kravanja, 2008, izvirni znanstveni članek

Opis: Optimization problems for the design and synthesis of flexible chemical processes are often associated with highly discretized models. The ultimate goal of this work is to significantly reduce the set of uncertain parameter points used in these problems. To accomplish the task, an approach was developed for identifying the minimum set of critical points needed for flexible design. Critical points in this work represent those values of uncertain parameters that determine optimal overdesign of process, so that feasible operation is assured within the specified domain of uncertain parameters. The proposed approach identifies critical values of uncertain parameters a-priori by the separate maximization of each design variable, together with simultaneous optimization of the economic objective function. During this procedure, uncertain parameters are transformed into continuous variables. Three alternative methods are proposed within this approach: the formulation based on Karush-Kuhn-Tucker (KKT) optimality conditions, the iterative two-level method, and the approximate one-level method. The identified critical points are then used for the discretization of infinite uncertain problems, in order to obtain the design with the optimum objective function and flexibility index at unity. All three methods can identify vertex or even nonvertex critical points, whose total number is less than or equal to the number of design variables, which represents a significant reduction in the problem's dimensionality. Some examples are presented illustrating the applicability and efficiency of the proposed approach, as well as the role of the critical points in the optimization of design problems under uncertainty.
Ključne besede: chemical processing, process synthesis, flexibility, design, critical point, vertex, nonvertex
Objavljeno: 01.06.2012; Ogledov: 1014; Prenosov: 50
URL Povezava na celotno besedilo

Distance-balanced graphs
Janja Jerebic, Sandi Klavžar, Douglas F. Rall, 2005

Opis: V članku so vpeljani razdaljno uravnoteženi grafi kot grafi, v katerih ima vsaka povezava ▫$uv$▫ naslednjo lastnost: število točk, ki so bližje ▫$u$▫ kot ▫$v$▫, je enako kot število točk, ki so bližje ▫$v$▫ kot ▫$u$▫. Dobljene so osnovne lastnosti teh grafov. Novi koncept je povezan z grafovskimi simetrijami, študirane so tudi lokalne operacije na grafih glede na razdaljno uravnoteženost. Karakterizirani so razdaljno uravnoteženi kartezični in leksikografski produkti grafov. Postavljenih je več odprtih problemov.
Ključne besede: matematika, teorija grafov, razdalja, razdaljno uravnoteženi grafi, produkti grafov, povezanost, mathematics, graph theory, graph distance, distance-balanced graphs, graph products, connectivity
Objavljeno: 10.07.2015; Ogledov: 493; Prenosov: 46
URL Povezava na celotno besedilo

Edge, vertex and mixed fault-diameters
Iztok Banič, Rija Erveš, Janez Žerovnik, 2008

Opis: Let ▫${mathcal{D}}^E_q(G)$▫ denote the diameter of a graph ▫$G$▫ after deleting any of its ▫$q$▫ edges, and ▫${mathcal{D}}^V_p(G)$▫ denote the diameter of ▫$G$▫ after deleting any of its ▫$p$▫ vertices. We prove that ▫${mathcal{D}}^E_a(G) le {mathcal{D}}^V_a(G) + 1$▫ a for all meaningful ▫$a$▫. We also define mixed fault diameter ▫${mathcal{D}}^M_{(p,q)}(G)$▫, where ▫$p$▫ vertices and ▫$q$▫ edges are deleted at the same time. We prove that for ▫$0 < l le a$▫, ▫${mathcal{D}}^E_a(G) le {mathcal{D}}^M_{(a-l,l)}(G) le {mathcal{D}}^V_a(G) + 1$▫, and give some examples.
Ključne besede: matematika, teorija grafov, povezanost, mathematics, (vertex)-connectivity, edge-connectivity, (vertex) fault-diameter, edge-fault diameter, interconnection network
Objavljeno: 10.07.2015; Ogledov: 325; Prenosov: 46
URL Povezava na celotno besedilo

Graphʼs theory approach for searching the shortest routing path in RIP protocol
Saša Klampfer, Jože Mohorko, Žarko Čučej, Amor Chowdhury, 2012, izvirni znanstveni članek

Opis: Routing is a problem domain with an infinite number of final-solutions. One of the possible approaches to solving such problems is using graph theory. This paper presents mathematical analysis methodologies based on circular graphs for solving a shortest path routing problem. The problem is focused on searching for the shortest path within a circular graph. Such a search coincides with the network routing problem domain. In this paper, we introduce in the detail all necessary parts needed to understand such an approach. This includes: definition of the routing problem domain, introduction to circular graphs and their usage, circular graphʼs properties, definition of walks through a circular graph, searching and determining the shortest path within a circular graph, etc. The state of the art routing methods, implemented in contemporary highly sophisticated routers, includes well-known weight-based algorithms and distance-vectors-based algorithms. The proposed solution can be placed between the two abovementioned methods. Each of these known methods strives for optimal results, but each of them also has its own deficiencies, which should be rectified with the proposed new method. This theoretically presented method is argued by a practical example and compared with the RIP (Routing Information Protocol) technique, where we look for the shortest path and possible walks through a specified circular graph.
Ključne besede: circular graphs, shortest path, graph diameter, walk through, CIGRP, connectivity matrix, network topology, symmetry, fully connected graph
Objavljeno: 10.07.2015; Ogledov: 922; Prenosov: 43
URL Povezava na celotno besedilo

On the k-path vertex cover of some graph products
Marko Jakovac, Andrej Taranenko, 2013, izvirni znanstveni članek

Opis: A subset S of vertices of a graph G is called a k-path vertex cover if every path of order k in G contains at least one vertex from S. Denote by ▫$psi_k$▫(G) the minimum cardinality of a k-path vertex cover in G. In this paper, improved lower and upper bounds for ▫$psi_k$▫ of the Cartesian and the strong product of paths are derived. It is shown that for ▫$psi_3$▫ those bounds are tight. For the lexicographic product bounds are presented for ▫$psi_k$▫, moreover ▫$psi_2$▫ and ▫$psi_3$▫ are exactly determined for the lexicographic product of two arbitrary graphs. As a consequence the independence and the dissociation number of the lexicographic product are given.
Ključne besede: matematika, teorija grafov, vozliščno pokritje, po poteh vozliščno pokritje, disociacijsko število, neodvisnostno število, grafovski produkti, mathematics, graph theory, vertex cover, path vertex cover, dissociation number, independence number, graph products
Objavljeno: 10.07.2015; Ogledov: 409; Prenosov: 7
URL Povezava na celotno besedilo

Edge, vertex and mixed fault diameters
Iztok Banič, Rija Erveš, Janez Žerovnik, 2009, izvirni znanstveni članek

Opis: Let ▫${mathcal{D}}^E_q(G)$▫ denote the maximum diameter among all subgraphs obtained by deleting ▫$q$▫ edges of ▫$G$▫. Let ▫${mathcal{D}}^V_p(G)$▫ denote the maximum diameter among all subgraphs obtained by deleting ▫$p$▫ vertices of ▫$G$▫. We prove that ▫${mathcal{D}}^E_a(G) leqslant {mathcal{D}}^V_a(G) + 1$▫ a for all meaningful ▫$a$▫. We also define mixed fault diameter ▫${mathcal{D}}^M_{(p,q)}(G)$▫, where ▫$p$▫ vertices and ▫$q$▫ edges are deleted at the same time. We prove that for ▫$0 < l leqslant a$▫, ▫${mathcal{D}}^E_a(G) leqslant {mathcal{D}}^M_{(a-ell,ell)}(G) leqslant {mathcal{D}}^V_a(G) + 1$▫, and give some examples.
Ključne besede: vertex-connectivity, edge-connectivity, vertex fault diameter, edge fault diameter, mixed fault diameter, interconnection network
Objavljeno: 10.07.2015; Ogledov: 384; Prenosov: 44
URL Povezava na celotno besedilo

Iskanje izvedeno v 0.28 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici