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

Opcije:
  Ponastavi


1 - 10 / 15
Na začetekNa prejšnjo stran12Na naslednjo stranNa konec
1.
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: 1144; Prenosov: 25
URL Povezava na celotno besedilo

2.
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: 954; Prenosov: 32
URL Povezava na celotno besedilo

3.
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: 281; Prenosov: 30
URL Povezava na celotno besedilo

4.
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: 382; Prenosov: 5
URL Povezava na celotno besedilo

5.
6.
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: 354; Prenosov: 23
URL Povezava na celotno besedilo

7.
8.
Maximal proper subgraphs of median graphs
Boštjan Brešar, Sandi Klavžar, 2007, izvirni znanstveni članek

Opis: Za medianski graf ▫$G$▫ in vozlišče ▫$v$▫, ki ni presečno, dokažemo, da je ▫$G-v$▫ medianski graf natanko tedaj, ko ▫$v$▫ ni center dvodelnega kolesa. To je nadalje ekvivalentno obstoju določene eliminacijske sheme za povezave, ki so incidenčne z ▫$v$▫. Rezultat implicira karakterizacijo po vozliščih kritičnih (po vozliščih polnih) medianskih grafov, ki so medianski grafi, katerih vsi podgrafi brez enega vozlišča niso medianski (so medianski). Podani sta tudi dve analogni karakterizaciji za primer odstranjevanja povezav.
Ključne besede: matematika, teorija grafov, medianski graf, podgraf brez enega vozlišča, dvodelno kolo, kvadratna povezava, mathematics, graph theory, median graph, vertex-deleted subgraph, bipartite wheel, square-eddge, square-dismantlable vertex
Objavljeno: 10.07.2015; Ogledov: 258; Prenosov: 20
URL Povezava na celotno besedilo

9.
Transitive, locally finite median graphs with finite blocks
Wilfried Imrich, Sandi Klavžar, 2008

Opis: V članku obravnavamo neskončne, lokalno končne, vozliščno-tranzitivne medianske grafe. Pokazano je, da končnost ▫$Theta$▫-razredov takih grafov ne zagotavlja končnosti blokov. Bloki pa postanejo neskončni, če nadalje nobeno končno zaporedje ▫$Theta$▫-kontrakcij ne naredi novih prereznih vozlišč. Dokazano je, da obstaja končno mnogo vozliščno-tranzitivnih medianskih grafov fiksne stopnje, ki imajo končne bloke. Konstruirana je neskončna družina vozliščno-tranzitivnih medianskih grafov z intranzitivnimi bloki. Podan je tudi seznam vseh vozliščno-tranzitivnih medianskih grafov stopnje 4.
Ključne besede: teorija grafov, medianski grafi, neskočni grafi, vozliščno-tranzitivni grafi, graph theory, median graphs, infinite graphs, vertex-transitive graphs
Objavljeno: 10.07.2015; Ogledov: 283; Prenosov: 29
URL Povezava na celotno besedilo

10.
Transitive, locally finite median graphs with finite blocks
Wilfried Imrich, Sandi Klavžar, 2009, izvirni znanstveni članek

Opis: V članku obravnavamo neskončne, lokalno končne, vozliščno-tranzitivne medianske grafe. Pokazano je, da končnost ▫$Theta$▫-razredov takih grafov ne zagotavlja končnosti blokov. Bloki pa postanejo neskončni, če nadalje nobeno končno zaporedje ▫$Theta$▫-kontrakcij ne naredi novih prereznih vozlišč. Dokazano je, da obstaja končno mnogo vozliščno-tranzitivnih medianskih grafov fiksne stopnje, ki imajo končne bloke. Konstruirana je neskončna družina vozliščno-tranzitivnih medianskih grafov z intranzitivnimi bloki. Podan je tudi seznam vseh vozliščno-tranzitivnih medianskih grafov stopnje 4.
Ključne besede: teorija grafov, medianski grafi, neskočni grafi, vozliščno-tranzitivni grafi, graph theory, median graphs, infinite graphs, vertex-transitive graphs
Objavljeno: 10.07.2015; Ogledov: 300; Prenosov: 31
URL Povezava na celotno besedilo

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