Search

Abstract: The interconnection network considered in this paper is the folded hypercube that is an attractive variance of the well-known hypercube. The folded hypercube is superior to the hypercube in many criteria, such as diameter, connectivity and fault diameter. In this paper, we study the path embedding aspects, bipanconnectivity and -panconnectivity, of the -dimensional folded hypercube. A bipartite graph is bipanconnected if each pair of vertices and are joined by the bipanconnected paths that include a path of each length satisfying and is even, where is the number of vertices, and denotes the shortest distance between and . A graph is -panconnected if each pair of vertices and are joined by the paths that include a path of each length ranging from to . In this paper, we introduce a new graph called the Path-of-Ladders. By presenting algorithms to embed the Path-of-Ladders into the folded hypercube, we show that the -dimensional folded hypercube is bipanconnected for is an odd number. We also show that the -dimensional folded hypercube is strictly -panconnected for is an even number. That is, each pair of vertices are joined by the paths that include a path of each length ranging from to ; and the value reaches the lower bound of the problem. [Copyright &y& Elsevier]

Abstract: Given a finite set , and a hypergraph , the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for . This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618–628] gave an incremental quasi-polynomial-time algorithm for solving the hypergraph transversal problem. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same theoretical worst-case bound, practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the original algorithm can be used to obtain a stronger bound on the running time. More generally, we consider a monotone property over a bounded n-dimensional integral box. As an important application of the above hypergraph transversal problem, pioneered by Bioch and Ibaraki [Complexity of identification and dualization of positive Boolean functions, Inform. and Comput. 123 (1995) 50–63], we consider the problem of incrementally generating simultaneously all minimal subsets satisfying and all maximal subsets not satisfying , for properties given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time via a polynomial-time reduction to a generalization of the hypergraph transversal problem on integer boxes. In this paper we present an efficient implementation of this procedure, and present experimental results to evaluate our implementation for a number of interesting monotone properties . [Copyright &y& Elsevier]

Given a family F of graphs, let Free ( F ) be the class of graphs that do not contain any member of F as an induced subgraph. When F is a set of four-vertex graphs the complexity of the vertex coloring problem in Free ( F ) is known, with three exceptions: F = { claw , 4 K 1 } , F = { claw , 4 K 1 , co-diamond } , and F = { C 4 , 4 K 1 } . In this paper, we study the coloring problem for Free (claw, 4 K 1 ). We solve the vertex coloring problem for a subclass of Free (claw, 4 K 1 ) which contains the class of 4 K 1 -free line graphs. [ABSTRACT FROM AUTHOR]

Abstract: This paper proposes a novel by-example texture synthesis algorithm. Unlike most present algorithms whose synthesized textures of different sizes must be stored in memory until rendering, our results are compactly stored as paths of the generative graphs. This is achieved by adapting the graph-based synthesis framework to be suitable for arbitrary types of textures. Two synthesis processes are carried out successively to grow the texture strip by strip to the desired horizontal and vertical dimensions, each of which is cast as a constrained shortest path problem that can be solved efficiently by our proposed algorithm. The strips are formed by consecutive cuts which are precomputed in the preprocessing step, and are selected with a redesigned mechanism accounting for both global and local matching errors. The variances make the graph-based synthesis framework also applicable to a wide variety of textures besides architectural textures, and the synthesis quality for them is greatly improved. [Copyright &y& Elsevier]

Abstract: In this paper, we address the problem of diagnosing the behaviors of interest in discrete-event systems. To this end, we introduce the notion of language-diagnosability, based on language specifications that generalizes diagnosability based on event specifications. A polynomial-time algorithm for verifying language-diagnosability is developed. Building upon the verification algorithm, we develop a polynomial-time algorithm for computing the worst case detection delay of a given system. The computation of the worst case detection delay involves the shortest path computation of a weighted, directed graph. We exploit a special weighting structure of the graph resulting from the verification algorithm, which enables an algorithm with a lower complexity than the commonly used Bellman–Ford shortest path algorithm. [Copyright &y& Elsevier]

Abstract: Golumbic, Kaplan, and Shamir [Graph sandwich problems, J. Algorithms 19 (1995) 449–473], in their paper on graph sandwich problems published in 1995, left the status of the sandwich problems for strongly chordal graphs and chordal bipartite graphs open. It was recently shown [C.M.H. de Figueiredo, L. Faria, S. Klein, R. Sritharan, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Theoret. Comput. Sci., accepted for publication] that the sandwich problem for strongly chordal graphs is NP-complete. We show that given graph G with a proper vertex coloring c, determining whether there is a supergraph of G that is chordal bipartite and also is properly colored by c is NP-complete. This implies that the sandwich problem for chordal bipartite graphs is also NP-complete. [Copyright &y& Elsevier]

Abstract: The coefficient of fragmentability of a class of graphs measures the proportion of vertices that need to be removed from the graphs in the class in order to leave behind bounded sized components. We have previously given bounds on this parameter for the class of graphs satisfying a given constant bound on maximum degree. In this paper, we give fragmentability bounds for some classes of graphs of bounded average degree, as well as classes of given thickness, the class of -colourable graphs, and the class of n-dimensional cubes. In order to establish the fragmentability results for bounded average degree, we prove that the proportion of vertices that must be removed from a graph of average degree at most in order to leave behind a planar subgraph (in fact, a series-parallel subgraph) is at most , provided or the graph is connected and . The proof yields an algorithm for finding large induced planar subgraphs and (under certain conditions) a lower bound on the size of the induced planar subgraph it finds. This bound is similar in form to the one we found for a previous algorithm we developed for that problem, but applies to a larger class of graphs. [Copyright &y& Elsevier]

Abstract: Let be the collection of all simple graphs with vertices and edges, and for let be the chromatic polynomial of . A graph is said to be optimal if another graph does not exist with for all , with strict inequality holding for some . In this paper we derive necessary conditions for bipartite graphs to be optimal, and show that, contrarily to the case of lower bounds, one can find values of and for which optimal graphs are not unique. We also derive necessary conditions for bipartite graphs to have the greatest number of cycles of length 4. [Copyright &y& Elsevier]

Abstract: In this paper we investigate weighted cross-intersecting families: if are given constants, we want to find the maximum of for uniform cross-intersecting families. We determine the maximum sum, even if we have restrictions of the size of . As corollaries, we will obtain some new bounds on the shadows and the shades of uniform families. We give direct proofs for these bounds, as well, and show that the theorems for cross-intersecting families also follow from these results. Finally, we will generalize the LYM inequality not only for cross-intersecting families, but also for arbitrary Sperner families. [Copyright &y& Elsevier]

Abstract: The problem of computing the similarity of two run-length encoded strings has been studied for various scoring metrics. Many algorithms have been developed for the longest common subsequence metric and some algorithms for the Levenshtein distance metric and the weighted edit distance metric. In this paper we consider similarity based on the affine gap penalty metric which is a more general and rather complicated scoring metric than the weighted edit distance. To compute the similarity in this model efficiently, we convert the problem into a path problem on a directed acyclic graph and use some properties of maximum paths in this graph. We present an time algorithm for computing the similarity of two run-length encoded strings in the affine gap penalty model, where and are the lengths of given two strings whose run-length encoded lengths are and , respectively. [Copyright &y& Elsevier]

Abstract: Multiscale models of linear dynamic systems offer a representation that links states at different time scales over distinct time periods. As such they allow a natural bridging of scales (ranges of frequencies) and time, and are more attractive than models defined in the time- or frequency-domain, alone. The term “multiscale model”, as used in this two-part series, is quite different from the notion of a “multiscale model”, as this is used in recent publications, where in essence such model bridges the states of a system at two distinct scales (an atomistic scale of fast elementary phenomena, and a macroscopic scale characterizing slow continuum-based physics), described by two distinctly different physical models. The multiscale dynamic models, introduced in this paper, link state dynamics over a number of distinct time scales, and are in essence “multiresolution” facets of a single model. The outgrowth of a series of developments, which came about with the advent of the wavelet decomposition for the analysis of discrete signals, multiscale models are defined on dyadic trees, which span the time-scale space. The nodes of such trees are used to index the values of states, inputs and outputs, modeling errors, and measurement errors of dynamic systems. These values are localized in both time and scale (range of frequencies), and thus they offer a hybrid domain that is particularly conducive for estimation and control problems. In Part 1 of this series, which focuses on the foundations of a multiscale systems theory, we will describe the generation of multiscale models from their time-domain counterparts, and develop conditions governing their stability, controllability and observability. In addition, we will address the development of algorithms for the solution of basic problems, such as: optimal control, state estimation, and optimal fusion of measurements and control actions at various scales. It will be shown that multiscale models lend themselves nicely to construction of very effective parallelizable algorithms. In Part 2 of this series, we will apply all these developments to the formulation of a Multiscale Model Predictive Control (MS-MPC) approach and we will show that MS-MPC is a more attractive framework for the design and implementation of multivariable control systems. [Copyright &y& Elsevier]

Abstract: We study algorithms for and its generalized version , the problem of computing the number of satisfying assignments of a set of propositional clauses . For this purpose we consider the clauses given by their incidence graph, a signed bipartite graph , and its derived graphs and . It is well known, that, given a graph of tree-width k, a k-tree decomposition can be found in polynomial time. Very recently Oum and Seymour have shown that, given a graph of clique-width k, a -parse tree witnessing clique-width can be found in polynomial time. In this paper we present an algorithm for for formulas of bounded tree-width k which runs in time , where n is the size of the input. The main ingredient of the algorithm is a splitting formula for the number of satisfying assignments for a set of clauses where the incidence graph is a union of two graphs and with a shared induced subgraph H of size at most k. We also present analogue improvements for algorithms for formulas of bounded clique-width which are given together with their derivation. This considerably improves results for , and hence also for SAT, previously obtained by Courcelle et al. [On the fixed parameter complexity of graph enumeration problems definable in monadic second order logic, Discrete Appl. Math. 108 (1–2) (2001) 23–52]. [Copyright &y& Elsevier]

Abstract: A graph (digraph) with a set of terminals is called inner Eulerian if each nonterminal node has even degree (resp. the numbers of edges entering and leaving are equal). Cherkassky and Lovász, independently, showed that the maximum number of pairwise edge-disjoint T-paths in an inner Eulerian graph G is equal to , where is the minimum number of edges whose removal disconnects s and . A similar relation for inner Eulerian digraphs was established by Lomonosov. Considering undirected and directed networks with “inner Eulerian” edge capacities, Ibaraki, Karzanov, and Nagamochi showed that the problem of finding a maximum integer multiflow (where partial flows connect arbitrary pairs of distinct terminals) is reduced to maximum flow computations and to a number of flow decompositions. In this paper we extend the above max–min relation to inner Eulerian bidirected graphs and inner Eulerian skew-symmetric graphs and develop an algorithm of complexity for the corresponding capacitated cases. In particular, this improves the best known bound for digraphs. Our algorithm uses a fast procedure for decomposing a flow with sources and sinks in a digraph into the sum of one-source-one-sink flows. [Copyright &y& Elsevier]

Abstract: Fractal dimension is a suitable tool for analyzing the nonlinear behaviour and state of the dynamical systems. The algorithms of fractal dimension methods have weak ability to the estimation of complexity in the irregular graphs. In this paper we propose a new algorithm based on the size measure relationship (SMR) method, quantifying the dimensional behaviour of irregular rectifiable graphs with minimum time complexity. The evidence for the suitability (equality with the nature of dimension) of the algorithm is presented. [Copyright &y& Elsevier]

Abstract: We give a competitive algorithm to identify all d defective edges in a hypergraph with d unknown. Damaschke did the case for 2-graphs, Triesch extended the case to r-graphs, and Johann did the general d case for 2-graphs. So ours is the first attempt to solve the searching for defective edges problem in its full generality. Further, all the above three papers assumed d known. We give a competitive algorithm where d is unknown. [Copyright &y& Elsevier]

Abstract: In this paper, a new algorithm for the computation of the connectivity in kinematic chains having total and partial mobility is presented. The adopted algorithm, based on graph theory, is able, firstly, to recognize when a kinematic chain has partial mobility and, then, to find the corresponding connectivity matrix. The new strategy consists in a recursive procedure, called “circuits gradual freezing”, which detects the sets of independent loops for each grade of recursion, and assigns to each pair of vertices the weighted distance. Results have shown the feasibility of the new approach and its better performance in some difficult cases. [Copyright &y& Elsevier]

Abstract: The class of doubly chordal graphs, which is a subclass of chordal graphs and a superclass of strongly chordal graphs, arises in many application areas. Many NP-complete optimization problems on chordal graphs like domination and Steiner tree can be solved in polynomial time on doubly chordal graphs using doubly perfect elimination ordering of vertices. In this paper, we show that the computation of a doubly perfect elimination ordering in a doubly chordal graph with n vertices and m edges can be done in time using processors on the CRCW PRAM model. [Copyright &y& Elsevier]

Abstract: Our goal in this paper is the development of fast algorithms for recognizing general classes of graphs. We seek algorithms whose complexity can be expressed as a linear function of the graph size plus an exponential function of k, a natural parameter describing the class. In particular, we consider the class , where for each graph G in , the removal of a set of at most k vertices from G results in a graph in the base graph class . (If is the class of edgeless graphs, is the class of graphs with bounded vertex cover.) When is a minor-closed class such that each graph in has bounded maximum degree, and all obstructions of (minor-minimal graphs outside ) are connected, we obtain an recognition algorithm for , where g and f are constants (modest and quantified) depending on the class . If is the class of graphs with maximum degree bounded by (not closed under minors), we can still obtain a running time of for recognition of graphs in . Our results are obtained by considering bounded-degree minor-closed classes for which all obstructions are connected graphs, and showing that the size of any obstruction for is , where t is a bound on the size of obstructions for . A trivial corollary of this result is an upper bound of on the number of vertices in any obstruction of the class of graphs with vertex cover of size at most k. These results are of independent graph-theoretic interest. [Copyright &y& Elsevier]

Abstract: A graphic sequence is said to be potentially -graphic, if has a realization G containing , a clique of vertices, as a subgraph. In this paper, we give two simple sufficient conditions for a graphic sequence to be potentially -graphic. We also show that the two sufficient conditions imply a theorem due to Rao [An Erdös-Gallai type result on the clique number of a realization of a degree sequence unpublished.], a theorem due to Li et al [The Erdös–Jacobson–Lehel conjecture on potentially -graphic sequences is true, Sci. China Ser. A 41 (1998) 510–520.], the Erdös–Jacobson–Lehel conjecture on which was confirmed (see [Potentially -graphical degree sequences, in: Y. Alavi et al. (Eds.), Combinatorics, Graph Theory, and Algorithms, vol. 1, New Issues Press, Kalamazoo Michigan, 1999, pp. 451–460; The smallest degree sum that yields potentially -graphic sequences, J. Graph Theory 29 (1998) 63–72; An extremal problem on the potentially -graphic sequence, Discrete Math. 212 (2000) 223–231; The Erdös–Jacobson–Lehel conjecture on potentially -graphic sequences is true, Sci. China Ser. A 41 (1998) 510–520.]) and the Yin–Li–Mao conjecture on [An extremal problem on the potentially -graphic sequences, Ars Combin. 74 (2005) 151–159.], where is a graph obtained by deleting one edge from . [Copyright &y& Elsevier]

Abstract: In this extended abstract we state some definitions and results from our earlier paper [C.Paul and J.A.Telle. New tools and simpler algorithms for branchwidth. In European Symposium on Algorithm - ESA 2005. To appear in Lecture Notes in Computer Science, 2005. Full draft avalaible as LIRMM RR 05-017] and use these to characterize the class of edge-maximal graphs of branchwidth k. Similarly to the maximal graphs of treewidth k (the k-trees) they turn out to be a subclass of chordal graphs where every minimal separator has size k. [Copyright &y& Elsevier]

Abstract: The -sparse Graph Sandwich Problem asks, given two graphs and , whether there exists a graph such that and G is -sparse. In this paper we present a polynomial-time algorithm for solving the Graph Sandwich Problem for -sparse graphs. [Copyright &y& Elsevier]

Abstract: In this paper we summarize some recent ideas in graph partitioning. We describe three algorithms to cluster vertices of a simple graph and we compare them according to their ability to recover classes initially introduced in random graphs. [Copyright &y& Elsevier]

Abstract: The main results of the paper are two dual algorithms bijectively mapping the set of spanning trees with internal activity 1 and external activity 0 of an ordered graph onto the set of acyclic orientations with adjacent unique source and sink. More generally, these algorithms extend to an activity-preserving correspondence between spanning trees and orientations. For certain linear orderings of the edges, they also provide a bijection between spanning trees with external activity 0 and acyclic orientations with a given unique sink. This construction uses notably an active decomposition for orientations of a graph which extends the notion of components for acyclic orientations with unique given sink. [Copyright &y& Elsevier]

Abstract: It has been a challenging open problem whether there is a polynomial time approximation algorithm for the VERTEX COVER problem whose approximation ratio is bounded by a constant less than 2. In this paper, we study the VERTEX COVER problem on graphs with perfect matching (shortly, VC-PM). We show that if the VC-PM problem has a polynomial time approximation algorithm with approximation ratio bounded by a constant less than 2, then so does the VERTEX COVER problem on general graphs. Approximation algorithms for VC-PM are developed, which induce improvements over previously known algorithms on sparse graphs. For example, for graphs of average degree 5, the approximation ratio of our algorithm is 1.414, compared with the previously best ratio 1.615 by Halldórsson and Radhakrishnan. [Copyright &y& Elsevier]

Abstract: Effective scheduling of operations in batch plants has a great potential for high economic returns, in which the formulation and optimal solution algorithm are the main issues of study. Petri-nets have proven to be a promising technique to solve many difficult problems associated with the modeling, formal analysis, design and coordination control of discrete event systems. One of the major advantages of using a Petri-net model is that the same model can be used for the analysis of behavioral properties and performance evaluation, as well as for the systematic construction of discrete event simulators and controllers. This paper aims to present a Petri-net based approach for the scheduling of operations in batch plants. Firstly, the short-term scheduling of batch plants is formulated using timed Petri-net. Secondly, the heuristic search algorithm for scheduling of batch plants is given, which is based on generating and checking the markings in the reachability tree of the Petri-net model. Finally, the novel formulation and algorithm are tested using two simulation case studies, and compared against traditional methods. [Copyright &y& Elsevier]

Abstract: In this paper, we describe a new simple linear time algorithm to recognize cographs. Cographs are exactly the -free graphs (where denotes the path with 4 vertices). The recognition process works in two steps. First, we use partition refinement techniques to produce a factorizing permutation, i.e., an ordering of the vertices in which the strong modules appear consecutively. Then a very simple test algorithm is provided to check whether the given graph is a cograph, using a single sweep of the permutation obtained in the first step. [Copyright &y& Elsevier]

Abstract: The f-cost of a tree decomposition for a function is defined as . This measure associates with the running time or memory use of some algorithms that use the tree decomposition. In this paper, we investigate the problem to find tree decompositions of minimum f-cost. A function is fast, if for every : . We show that for fast functions f, every graph G has a tree decomposition of minimum f-cost that corresponds to a minimal triangulation of G; if f is not fast, this does not hold. We give polynomial time algorithms for the problem, assuming f is a fast function, for graphs that have a polynomial number of minimal separators, for graphs of treewidth at most two, and for cographs, and show that the problem is NP-hard for bipartite graphs and for cobipartite graphs. We also discuss results for a weighted variant of the problem derived of an application from probabilistic networks. [Copyright &y& Elsevier]

Extensive facility location models on graphs deal with the location of a special type of subgraphs such as paths, trees or cycles and can be considered as extensions of classical point location models. Variance is one of the measures applied in models in which some equality requirement is imposed. In this paper the problem of locating a minimum variance path in a tree network is addressed, and an O(n2 log n) time algorithm is proposed. [Copyright &y& Elsevier]

Abstract: Given a graph, a connected dominating set is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum connected dominating set is such a vertex subset with minimum cardinality. In this paper, we present a new one-step greedy approximation with performance ratio where is the maximum degree in the input graph. The interesting aspect is that the greedy potential function of this algorithm is not supmodular while all previously known one-step greedy algorithms with similar performance have supmodular potential functions. [Copyright &y& Elsevier]

An identifying code of a graph is a subset of vertices C such that the sets B(v)∩C are all nonempty and different. In this paper, we investigate the problem of finding identifying codes of minimum cardinality in strips and finite grids. We first give exact values for the strips of height 1 and 2, then we give general bounds for strips and finite grids. Finally, we give a sublinear algorithm which finds the minimum cardinality of an identifying code in a restricted class of graphs which includes the grid. [Copyright &y& Elsevier]