| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 10 / 15
First pagePrevious page12Next pageLast page
1.
Acceleration of sweep-line technique by employing smart quicksort
David Podgorelec, Gregor Klajnšek, 2005, original scientific article

Abstract: 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.
Keywords: computational geometry, quicksort, smart quicksort, sweep-line, smart quicksort, polygon triangualation, vertex sort
Published: 01.06.2012; Views: 1206; Downloads: 47
URL Link to full text

2.
Identification of critical points for the design and synthesis of flexible processes
Zorka Novak-Pintarič, Zdravko Kravanja, 2008, original scientific article

Abstract: 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.
Keywords: chemical processing, process synthesis, flexibility, design, critical point, vertex, nonvertex
Published: 01.06.2012; Views: 1023; Downloads: 52
URL Link to full text

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

Abstract: 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.
Keywords: matematika, teorija grafov, povezanost, mathematics, (vertex)-connectivity, edge-connectivity, (vertex) fault-diameter, edge-fault diameter, interconnection network
Published: 10.07.2015; Views: 335; Downloads: 48
URL Link to full text

4.
On the k-path vertex cover of some graph products
Marko Jakovac, Andrej Taranenko, 2013, original scientific article

Abstract: 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.
Keywords: 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
Published: 10.07.2015; Views: 423; Downloads: 7
URL Link to full text

5.
6.
Edge, vertex and mixed fault diameters
Iztok Banič, Rija Erveš, Janez Žerovnik, 2009, original scientific article

Abstract: 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.
Keywords: vertex-connectivity, edge-connectivity, vertex fault diameter, edge fault diameter, mixed fault diameter, interconnection network
Published: 10.07.2015; Views: 393; Downloads: 46
URL Link to full text

7.
8.
Maximal proper subgraphs of median graphs
Boštjan Brešar, Sandi Klavžar, 2007, original scientific article

Abstract: 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.
Keywords: 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
Published: 10.07.2015; Views: 291; Downloads: 43
URL Link to full text

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

Abstract: 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.
Keywords: teorija grafov, medianski grafi, neskočni grafi, vozliščno-tranzitivni grafi, graph theory, median graphs, infinite graphs, vertex-transitive graphs
Published: 10.07.2015; Views: 339; Downloads: 50
URL Link to full text

10.
Transitive, locally finite median graphs with finite blocks
Wilfried Imrich, Sandi Klavžar, 2009, original scientific article

Abstract: 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.
Keywords: teorija grafov, medianski grafi, neskočni grafi, vozliščno-tranzitivni grafi, graph theory, median graphs, infinite graphs, vertex-transitive graphs
Published: 10.07.2015; Views: 363; Downloads: 57
URL Link to full text

Search done in 0.24 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica