CHINESE POSTMAN PROBLEM WITH PRIORITIES (2008)
Tomaž Kramberger, Janez Žerovnik
Abstract. A generalization of the Chinese Postman Problem is considered, in which a linear order on a set of important nodes is given and the task is to traverse all edges at least once in such a way...
A numerical characterization of modified Hamori curve representation of DNA sequences (2008)
We present new numerical characterization of DNA sequences that is based on the modified graphical representation proposed by Hamori. While Hamori embeds the sequence into Euclidean space, we use...
The fault-diameter of Cartesian products (2008)
Let $G$ be a $k$-connected graph and ${\mathcal{D}}_C(G)$ denote the maximum diameter of $G$ after deleting any of its $c
Perfect codes in direct products of cycles - a complete characterization (2008)
Let $G = \times^n_{i=1}C_{\ell_i}$ be a direct product of cycles. It is known that for any $r \le 1$, and any $n \le 2$, each connected component of $G$ contains a so-called canonical $r$-perfect...
#An #optimal permutation routing algorithm on full-duplex hexagonal networks (2008)
Žerovnik, Janez, Saun Walls, Ignasi
Zahtevnost permutacijskega usmerjanja je standarden test za primernost topologije za komunikacijsko omrežje. V članku je pokazano, da je mogoče na heksagonalnih mrežah vsako permutacijsko...
Žerovnik, Janez, Kramberger, Tomaž
This article deals with the specific road phenomenon in winter, when driving conditions suddenly become significantly worse, although the global weather conditions have not significantly altered....
Circular chromatic number of triangle-free hexagonal graphs (2008)
An interesting connection between graph homomorphisms to odd cycles and circular chromatic number is presented. By using this connection, bounds for circular chromatic number of triangle-free...
Edge fault-diameter of Cartesian graph bundles (2008)
Žerovnik, Janez, Banič, Iztok, Erveš, Rija
We generalize the result of for two factors to Cartesian graph bundles. As a k-edge connected graph remains connected if up to k−1 edges are missing, we study the diameter of a graph with any...
A note on n-tuple colourings and circular colourings of planar graphs with large odd girth (2007)
The existance of planar graphs with odd girth 2k + 1 and high girth that cannot be (2k + 1, k)-coloured was left as an open question by Klostermeyer and Zang. In this note we show that such graphs...
The Hosoya-Wiener Polynomial of Weighted Trees (2007)
Formulas for the Wiener number and the Hosoya-Wiener polynomial of edge and vertex weighted graphs are given in terms of edge and path contributions. For a rooted tree, the Hosoya- Wiener polynomial...
Best insertion algorithm for resource-constrained project scheduling problem (2007)
This paper considers heuristics for well known resource-constrained project scheduling problem (RCPSP). First a feasible schedule is constructed using randomized best insertion algorithm. The...
Hybrid local search techniques for the resource-constrained project scheduling problem (2007)
Pesek, Igor, Žerovnik, Janez, Andrea, Schaerf
This paper proposes a local search algorithm that makes use of a complex neighborhood relation based on a hybridization with a constructive heuristics for the classical resource-constrained project...
The Hosoya-Wiener polynomial of weighted trees (2007)
Formulas for the Wiener number and the Hosoya-Wiener polynomial of edge and vertex weighted graphs are given in terms of edge and path contributions. For a rooted tree, the Hosoya-Wiener polynomial...
Weak reconstruction of strong product graphs (2007)
We prove that the class of nontrivial connected strong product graphs is weakly reconstructible. We also show that any nontrivial connected thin strong product graph can be uniquely reconstructed...
Priority constrained Chinese postman problem (2007)
Kramberger, Tomaž, Žerovnik, Janez
In early ninety sixties of the last century the Chinese mathematician Mei-Ko Kwan (M. Guan) proposed a method that could be used to minimize the lengths of routes walked by mail carriers. In several...
Frequency assignment - case study. Part I, Problem definition (2007)
Pesek, Igor, Saje, Iztok, Žerovnik, Janez
The rapid development of celular telephone networks in recent years has increased the need for good solution techniques for the frequency assignment problem on cellular networks. The solution methods...
Frequency assignment - case study. Part II, Computational results (2007)
Pesek, Igor, Saje, Iztok, Žerovnik, Janez
The rapid development of celular telephone networks in recent years has increased the need for good solution techniques for the frequency assignment problem on cellular networks. The solution methods...
Optimal permutation routing on mesh networks (2007)
Sau Walls, Ignasi, Žerovnik, Janez
Permutation routing is used as one of the standard tests of routing algorithms. In the permutation routing problem, each processor is the origin of at most one packet and the destination of no more...
Pascal Workshop, Complex Objects Visualization 2005 - COV2005, Proceedings (2006)
Pisanski, Tomaž, Horvat, Boris, Žerovnik, Janez, Mladenić, Dunja, Grobelnik, Marko, Anžič, Tina, ...
Pascal workshop on Complex Object Visualization COV-2005 brought together a group of researchers from various branches of Mathematics and Computer Science focused around a common theme that arises in...
On Algebraic and Geometric Kekulé Structures in Benzenoid Rotagraphs (2006)
Graovac, Ante, Vukičević, Damir, Žerovnik, Janez
Recently introduced algebraic Kekulé structures (AKS) describe the π-electron distribution within rings of a conjugated network. The ratio of the AKS count to the classical Kekulé structures count...
This paper considers two algorithms for well known resource-constrained project scheduling problem (RCPSP). Feasible schedule is constructed using randomized best insertion algorithm and examining...
Numerical characterization of modified Hamori curve representation of DNA sequences (2006)
The length of DNA sequences make graphical visualization techniques useful for bioscientists. An advantage of such representations is that they allow visual inspection, helping in recognizing major...
Best insertion algorithm for resource constrained project scheduling problem (2006)
This paper considers heuristics for well known resource-constrained project scheduling problem (RCPSP). First a feasible schedule is constructed using randomized best insertion algorithm. The...
On some simple heuristics for combinatorial optimization (2006)
Many combinatorial optimization problems that are of practical and theoretical interest are NP-hard. Assuming P≠NP, there is no efficient (i.e. polynomial time) algorithm which can solve instances...
Fault-diameter of Cartesian graph bundles (2006)
Cartesian graph bundles is a class of graphs that is a generalization of the Cartesian graph products. Let $G$ be a $k_G$-connected graph and $\DD_c(G)$ denote the diameter of $G$ after deleting any...
On domination numbers of graph bundles (2006)
Let $\gamma (G)$ be the domination number of a graph $G$. It is shown that for any $k\ge 0$ there exists a Cartesian graph bundle $B\bun F$ such that $\gamma (B\bun F)= \gamma(B) \gamma (F)-2k$. The...
An optimal message routing algorithm for circulant networks (2006)
Dobravec, Tomaž, Žerovnik, Janez, Robič, Borut
A k-circulant network G(n; h1, h2, … , hk) is an undirected graph where the node set is $Z_n$ and the edges are given by $\{v,v\pm hi\}$. We present an optimal (i.e. using shortest paths) dynamic...
Fault-diameter of generalized Cartesian products (2006)
Cartesian graph bundles is a class of graphs that is a generalization of the Cartesian graph products. Let $G$ be a $k_G$-connected graph and $\DD_c(G)$ denote the diameter of $G$ after deleting any...
On the oriented network design problem (2006)
The cost of a network with a routing is defined as a sum of arc costs that depend on the capacity only. The capacity corresponds to the number of paths of the routing that traverse the arc. We sketch...
Visualization of graphs using their product stucture (2005)
Graphs are combinatorial structures given by a set of vertices and a set of edges giving the adjacencies between pairs of vertices. Drawing graphs nicely is a challenging task. If a graph has some...
Mixture of Vector Experts (2005)
Henderson, Matthew, Shawe-Taylor, John, Žerovnik, Janez
We describe and analyze an algorithm for predicting a sequence of n-dimensional binary vectors based on a set of experts making vector predictions in [0,1]^n. We measure the loss of individual...
2-local 3/4-competitive algorithm for multicoloring hexagonal graphs (2005)
An important optimization problem in the design of cellular networks is to assign sets of frequencies to transmitters to avoid unacceptable interference. A cellular network is generally modeled as a...
An algorithm for 12-[5]coloring of triangle-free hexagonal graphs (2005)
An important optimization problem in the design of cellular networks is to assign sets of frequencies to transmitters to avoid unacceptable interference. A cellular network is generally modeled as a...
Metaheuristics in Automated Storage and Retrieval Systems (2005)
This paper proposes the use of some metaheuristics to improve the performance of AS/RS; focusing attention on storage and retrieval policies, on-board storage capacity, S/R machine operation modes,...
A heuristic for the asymmetric traveling salesman problem (2005)
In this note we first give the results of tests of our algorithm on all ATSP instances of the TSPLIB library, which were available at the time of the experiment. The results we obtain are consistent...
Optimization of markers in clothing industry with randomized algorithms (2005)
Fister, Iztok, Žerovnik, Janez
Optimization of markers in clothing industry can be done by optimizing a sequence of markers, i.e. vectors of sizes by design which covers the work order, i.e. a matrix of sizes in corresponding...
Local Optimization Applied to a Volunteer Timetabling Problem (2005)
Borovinsek, Matej, Žerovnik, Janez
The time table assembly is problem in which the feasibility of solutions involves solution of a graph coloring problem while the quality of solution is obtained by optimization of a fitness function....
Chinese postman problem with priorities (2005)
Kramberger, Tomaz, Žerovnik, Janez
A generalization of the Chinese Postman Problem is considered, in which a linear order on a set of important nodes is given and the task is to traverse all edges at least once in such a way that the...
The obnoxious center problem on weighted cactus graphs. (2004)
The obnoxious center problem in a graph $G$ asks for a location on an edge of the graph such that the minimum weighted distance from this point to a vertex of the graph is as large as possible. An...
2-local 5/4-competitive algorithm for multicoloring triangle-free hexagonal graphs. (2004)
An important optimization problem in the design of cellular networks is to assign sets of frequencies to transmitters to avoid unacceptable interference. A cellular networks is generally modeled as a...
Experiments with a randomized algorithm for a frequency assignement problem. (2004)
The problems of assigning frequencies to transmitters can be naturally modelled by generalizations of graph coloring problems.We start with a randomized graph coloring algorithm of Petford and Welsh...
A heuristic for computing the domination number of triangulated planar graphs. (2004)
Žerovnik, Janez, Kaučič, Branko
A major problem in computer networks is the problem of determining optimal locations of resources. The optimality of a location of a resource may depend on many different objectives. Often this is...
Ants and graph coloring (2004)
Shawe-Taylor, John, Žerovnik, Janez
Ants algorithm is an evolutionary search method for solving combinatorial optimization problems. In this note we propose a version of the algorithm for coloring a graph with a fixed number of colors....
Ants and graph coloring (2004)
Shawe-Taylor, John, Žerovnik, Janez
Ants algorithm is an evolutionary search method for solving combinatorial optimization problems. In this note we propose a version of the algorithm for coloring a graph with a fixed number of colors....