A Tight Lower Bound for a Special Case of Quadratic 0–1 Programming

We consider a still NP-complete partial case of the unconstrained binary quadratic optimization problem that can be described in terms of an undirected graph with red edges having negative weights and green edges having positive weights. The maximum vertex degree of the graph is three. It can be assumed w.l.o.g. that every vertex is incident to a red and a green edge. We are looking for a vertex cover with respect to the red edges which covers a subset of green edges of total weight as small as possible. We prove that for all connected such graphs except a subclass of special graphs having exactly five green edges it is possible to find a vertex cover with respect to the red edges for which the total weight of uncovered green edges is at least 1/4 fraction of the total weight of all green edges.     

A linear-time algorithm for paired-domination problem in strongly chordal graphs

Let G=(V,E) be a simple graph without isolated vertices. A vertex set S⊆V is a paired-dominating set if every vertex in V−S has at least one neighbor in S and the induced subgraph G[S] has a perfect matching. In this paper, we present a linear-time algorithm to find a minimum paired-dominating set in strongly chordal graphs if the strong (elimination) ordering of the graph is given in advance.     

An improved algorithm for the p-center problem on interval graphs with unit lengths

The p-center problem is to locate p facilities in a network of n   demand points so as to minimize the longest distance between a demand point and its nearest facility. We consider this problem by modelling the network as an interval graph whose edges all have unit lengths. We present an O(n)$O(n)$ time algorithm for the problem under the assumption that the endpoints of the intervals are sorted, which improves on the existing best algorithm for the problem that has a run time of O(pn)$O(\mathit{pn})$.     

Selection of programme slots of television channels for giving advertisement: A graph theoretic approach

The present paper aims at developing a linear time algorithm to find a solution to the ‘maximum weight 1 colouring’ problem for an interval graph with interval weight. This algorithm has been applied to solve the problem that involves selecting different programme slots telecast on different television channels in a day so as to reach the maximum number of viewers. It is shown that all programmes of all television channels can be modelled as a weighted interval graph with interval numbers as weights. The programme slots are taken as the vertices of the graph and if the time durations of two programme slots have non-empty intersection, the corresponding vertices are considered to be connected by an edge. The number of viewers of a programme is taken as the weight of the vertex. In reality, the number of viewers of a programme is not a fixed one; generally, it lies in an interval. Thus, the weights of the vertices are taken as interval numbers. We assume that a company sets the objective of selecting the popular programme in different channels so as to make its commercial advertisement reach the maximum number of viewers. However, the constraint imposed is that all selected programmes are mutually exclusive in respect of time scheduling. The objective of the paper is, therefore, to helps the companies to select the programme slots, which are mutually exclusive with respect to the time schedule of telecasting time, in such a way that the total number of viewers of the selected programme slots rises to the optimum level. It is shown that the solution of this problem is obtained by solving the maximum weight colouring problem on an interval graph. An algorithm is designed to solve this optimization problem using O(n) time, where n represents the total number of programmes of all channels.     

The k-fundamental group of a closed k-surface

In this paper, we deal with the problem of computing the digital fundamental group of a closed k-surface by using various properties of both a (simple) closed k-surface and a digital covering map. To be specific, let be a simple closed k_i-curve with l_i elements in Z^n_i, i∈{1,2}. Then, the Cartesian product is not always a closed k-surface with some k-adjacency of Z^n₁+n₂. Thus, we provide a condition for to be a (simple) closed k-surface with some k-adjacency depending on the k_i-adjacency, i∈{1,2}. Besides, even if is not a closed k-surface, we show that the k-fundamental group of can be calculated by both a k-homotopic thinning and a strong k-deformation retract.     

Path multicoloring with fewer colors in spiders and caterpillars

We study a recently introduced path coloring problem with applications to wavelength assignment in all-optical networks with multiple fibers. In contrast to classical path coloring, it is, in this setting, possible to assign a color more than once to paths that pass through the same edge; the number of allowed repetitions per edge is given and the goal is to minimize the number of colors used. We present algorithms and hardness results for tree topologies of special interest. Our algorithms achieve approximation ratio of 2 in spiders and 3 in caterpillars, whereas the best algorithm for trees so far, achieves an approximation ratio of 4. We also study the directed version of the problem and show that it admits a 3-approximation algorithm in caterpillars, while it can be solved exactly in spiders.      

Solution methods and computational investigations for the Linear Bottleneck Assignment Problem

The Linear Bottleneck Assignment ProblemLBAP is analyzed from a computational point of view. Beside a brief review of known algorithms new methods are developed using only sparse subgraphs for their computation. The practical behaviour of both types of algorithms is investigated. The most promising algorithm consists of computing a maximum cardinality matching with all edge costs smaller than a previously determined bound and augmenting this matching to an assignment. The methods on sparse subgraphs are useful in the case of memory restrictions and are superior if the subgraph selection can be improved by some previously generated structure. Other treated questions are how to select a suitable subgraph for the new methods, how to deal with non regular data and what connections to asymptotic results for theLBAP can be detected. Supported by the SFB F003 ‘Optimierung und Kontrolle’, Bereich Diskrete Optimierung.     

On the coding of ordered graphs

Ordered graph and ordered graph isomorphism provide a natural representation of many objects in applications such as computational geometry, computer vision and pattern recognition. In the present paper we propose a coding procedure for ordered graphs that improves an earlier one based on Eulerian circuits of graphs in terms of both simplicity and computational efficiency. Using our coding approach, we show that the ordered graph isomorphism problem can be optimally solved in quadratic time, although no efficient (polynomial-bound) isomorphism algorithm for general graphs exists today. An experimental evaluation demonstrates the superior performance of the new method.     

An experimental evaluation of local search heuristics for graph partitioning

A common problem that arises in many applications is to partition the vertices of a graph intok subsets, each containing a bounded number of vertices, such that the number of graph edges with endpoints in different subsets is minimized. This paper describes an empirical study of the performance of various local search heuristics for thisk-way graph partitioning problem. The heuristics examined are local optimization, simulated annealing, tabu search, and genetic algorithms. In addition, the hierarchical hybrid approach is introduced, in which the problem is recursively decomposed into small pieces, to which local search heuristics are then applied.     

SpiNNaker: Fault tolerance in a power- and area- constrained large-scale neuromimetic architecture

SpiNNaker is a biologically-inspired massively-parallel computer designed to model up to a billion spiking neurons in real-time. A full-fledged implementation of a SpiNNaker system will comprise more than 10⁵ integrated circuits (half of which are SDRAMs and half multi-core systems-on-chip). Given this scale, it is unavoidable that some components fail and, in consequence, fault-tolerance is a foundation of the system design. Although the target application can tolerate a certain, low level of failures, important efforts have been devoted to incorporate different techniques for fault tolerance. This paper is devoted to discussing how hardware and software mechanisms collaborate to make SpiNNaker operate properly even in the very likely scenario of component failures and how it can tolerate system-degradation levels well above those expected.     

On ACC

We show that every languageL in the class ACC can be recognized by depth-two deterministic circuits with a symmetric-function gate at the root and AND gates of fan-in log ^O(1) n at the leaves, or equivalently, there exist polynomialsp _n (x ₁ ,..., x _n ) overZ of degree log ^O(1) n and with coefficients of magnitude and functionsh _n :Z{0,1} such that for eachn and eachx{0,1} ⁿ ,XL ^(x) =h _n (p _n (x ₁ ,...,x _n )). This improves an earlier result of Yao (1985). We also analyze and improve modulus-amplifying polynomials constructed by Toda (1991) and Yao (1985).     

Polynomial Approximation and Graph-Coloring

Consider a graph G=(V,E) of order n. In the minimum graph-coloring problem we try to color V with as few colors as possible so that no two adjacent vertices receive the same color. This problem is among the first ones proved to be intractable, and hence, it is very unlikely that an optimal polynomial-time algorithm could ever be devised for it. In this paper, we survey the main polynomial time approximation algorithms (the ones for which theoretical approximability bounds have been studied) for the minimum graph-coloring and we discuss their approximation performance and their complexity. Finally, we further improve the approximation ratio for graph-coloring. Received October 5, 2001; revised November 15, 2002 Published online: February 20, 2003     

The K r -Packing Problem

For a fixed integer r≥2, the K _r -packing problem is to find the maximum number of pairwise vertex-disjointK _r 's (complete graphs on r vertices) in a given graph. The K _r -factor problem asks for the existence of a partition of the vertex set of a graph into K _r 's. The K _r -packing problem is a natural generalization of the classical matching problem, but turns out to be much harder for r≥3 – it is known that for r≥3 the K _r -factor problem is NP-complete for graphs with clique number r [16]. This paper considers the complexity of the K _r -packing problem on restricted classes of graphs. We first prove that for r≥3 the K _r -packing problem is NP-complete even when restrict to chordal graphs, planar graphs (for r=3, 4 only), line graphs and total graphs. The hardness result for K ₃-packing on chordal graphs answers an open question raised in [6]. We also give (simple) polynomial algorithms for the K ₃-packing and the K _r -factor problems on split graphs (this is interesting in light of the fact that K _r -packing becomes NP-complete on split graphs for r≥4), and for the K _r -packing problem on cographs. Received September 27, 1999; revised August 14, 2000     

Measuring the network robustness by Monte Carlo estimation of shortest path length distribution

Two kinds of robustness measure for networks are introduced and applied to the road network systems in Japan. One is on the connectivity of randomly chosen pair of vertices, another is on the shortest path length between pair of connected vertices. We devise Monte Carlo methods for the computation of two measures.     

Volume Maximization and Orthoconvex Approximation of Orthogons

Let n axes-parallel hyperparallelepipeds (also called blocks) of the d-dimensional Euclidean space and a positive integer r be given. The volume maximization problem (VMP) selects at most r blocks such that the volume of their union becomes maximum. VMP is shown to be -hard in the 2-dimensional case and polynomially solvable for the line via a constrained critical path problem (CCPP) in an acyclic digraph. This CCPP leads to further well solvable special cases of the maximization problem. In particular, the following approximation problem (OAP) becomes polynomially solvable: given an orthogon P (i.e., a simple polygon in the plane which is a union of blocks) and a positive integer q, find an orthoconvex orthogon with at most q vertices and minimum area, which contains P. Received: September 7, 1998     

The complexity of deciding stability under FFS in the Adversarial Queueing model

We address the problem of deciding whether a given network is stable in the Adversarial Queueing Model when considering farthest-from-source (ffs) as the queueing policy to schedule the packets through its links. We show a characterisation of the networks which are stable under ffs in terms of a family of forbidden subgraphs. We show that the set of networks stable under ffs coincide with the set of universally stable networks. Since universal stability of networks can be checked in polynomial time, we obtain that stability under ffs can also be decided in polynomial time.     

Makespan minimization in preemptive two machine job shops

In this note we investigate the NP-complete problem of minimizing the makespan in a preemptive two machine job shop. We present a polynomial time approximation algorithm with worst case ratio 3/2 for this problem, and we also argue that this is the best possible result that can be derived via our line of approach.     

A linear algorithm for the pos/neg-weighted 1-median problem on a cactus

The 1-median problem on a network asks for a vertex minimizing the sum of the weighted shortest path distances from itself to all other vertices, each associated with a certain positive weight. We allow fornegative weights as well and devise an exact algorithm for the resulting ‘pos/neg-weighted’ problem defined on a cactus. The algorithm visits every vertex just once and runs thus in linear time. This research has been supported by the Spezialforschungsbereich F 003 ‘Optimierung und Kontrolle’, Projektbereich Diskrete Optimierung.     

A New Well-Solvable Class of PNS Problems

A manufacturing system consists of operating units which convert their input materials into their output materials. In the problem of designing a process network, we have to find a suitable network of operating units which produces the desired products from the given raw materials. If we consider this process network design problem from a structural point of view, then we obtain a combinatorial optimization problem called the Process Network Synthesis or (PNS) problem. It is known that the PNS problem is NP-complete. Here, a new method is presented to reduce the solution of some more difficult PNS problems to the solution of simpler ones, and using this method, a new well-solvable class of PNS problems is established. Received February 12, 1999; revised October 24, 2000     

More About Subcolorings

A subcoloring is a vertex coloring of a graph in which every color class induces a disjoint union of cliques. We derive a number of results on the combinatorics, the algorithmics, and the complexity of subcolorings. On the negative side, we prove that 2-subcoloring is NP-hard for comparability graphs, and that 3-subcoloring is NP-hard for AT-free graphs and for complements of planar graphs. On the positive side, we derive polynomial time algorithms for 2-subcoloring of complements of planar graphs, and for r-subcoloring of interval and of permutation graphs. Moreover, we prove asymptotically best possible upper bounds on the subchromatic number of interval graphs, chordal graphs, and permutation graphs in terms of the number of vertices. Received June 11, 2002; revised September 13, 2002 Published online: November 25, 2002 RID="*" ID="*" The work of HJB and FVF is sponsored by NWO-grant 047.008.006. FVF acknowledges support by EC contract IST-1999-14186, Project ALCOM-FT (Algorithms and Complexity – Future Technologies). Part of this work was done while FVF was visiting the University of Twente, and while he was a visiting postdoc at DIMATIA-ITI (supported by GAČR 201/99/0242 and by the Ministry of Education of the Czech Republic as project LN00A056). JN acknowledges support of ITI – the Project LN00A056 of the Czech Ministery of Education. GJW acknowledges support by the START program Y43-MAT of the Austrian Ministry of Science.