Parallel algorithms for permutation graphs

In this paper, parallel algorithms are presented for solving some problems on permutation graphs. The coloring problem is solved inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM. The weighted clique problem, the weighted independent set problem, the cliques cover problem, and the maximal layers problem are all solved with the same complexities. We can also show that the longest common subsequence problem belongs to the class NC.     

An efficient algorithm to find next-to-shortest path on permutation graphs

In this paper, we present an efficient algorithm to find next-to-shortest path between any pair of vertices u,v on permutation graphs with n vertices which runs in O(n ²) time.     

Sorting with networks of data structures

We consider the problem of sorting a permutation using a network of data structures as introduced by Knuth and Tarjan. In general the model as considered previously was restricted to networks that are directed acyclic graphs (DAGs) of stacks and/or queues. In this paper we study the question of which are the smallest general graphs that can sort an arbitrary permutation and what is their efficiency. We show that certain two-node graphs can sort in time Θ(n²) and no simpler graph can sort all permutations. We then show that certain three-node graphs sort in time Ω(n^3/2), and that there exist graphs of k nodes which can sort in time Θ(nlog_kn), which is optimal.     

A compact representation for permutation groups

A data structure is presented which enables an arbitary permutation group of degree n to be represented in O(n²) space. An algorithm is provided which, given a permutation group specified in the usual way as a set of generators, constructs the proposed representation in time O(n⁵). The data structure supports fast membership testing, and is more economical than those previously suggested, both in terms of its size and the time required for its initialisation. Essential use is made of the proposed data structure in an efficient algorithm for generating systems of coset representatives; this algorithm may be used to solve certain instances of the so-called “isomorph rejection” problem.     

Minimum 2-tuple dominating set of permutation graphs

For a fixed positive integer k, a k-tuple dominating set of a graph G=(V,E) is a subset D?V such that every vertex in V is dominated by at least k vertex in D. The k-tuple domination number γ _×k (G) is the minimum size of a k-tuple dominating set of G. The special case when k=1 is the usual domination. The case when k=2 was called double domination or 2-tuple domination. A 2-tuple dominating set D ₂ is said to be minimal if there does not exist any D′?D ₂ such that D′ is a 2-tuple dominating set of G. A 2-tuple dominating set D ₂, denoted by γ _×2(G), is said to be minimum, if it is minimal as well as it gives 2-tuple domination number. In this paper, we present an efficient algorithm to find a minimum 2-tuple dominating set on permutation graphs with n vertices which runs in O(n ²) time.     

On the domination number of the generalized Petersen graphs

Graph domination numbers and algorithms for finding them have been investigated for numerous classes of graphs, usually for graphs that have some kind of tree-like structure. By contrast, we study an infinite family of regular graphs, the generalized Petersen graphs G(n). We give two procedures that between them produce both upper and lower bounds for the (ordinary) domination number of G(n), and we conjecture that our upper bound ⌈3n/5⌉ is the exact domination number. To our knowledge this is one of the first classes of regular graphs for which such a procedure has been used to estimate the domination number.     

The weighted maximum independent set problem in permutation graphs

In this paper, sequential and parallel algorithms are presented to find a maximum independent set with largest weight in a weighted permutation graph. The sequential algorithm, which is designed based on dynamic programming, runs in timeO(nlogn) and requiresO(n) space. The parallel algorithm runs inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM.     

Localized and compact data-structure for comparability graphs

We show that every comparability graph of any two-dimensional poset over n elements (a.k.a. permutation graph) can be preprocessed in O(n) time, if two linear extensions of the poset are given, to produce an O(n) space data-structure supporting distance queries in constant time. The data-structure is localized and given as a distance labeling, that is each vertex receives a label of O(logn) bits so that distance queries between any two vertices are answered by inspecting their labels only. This result improves the previous scheme due to Katz, Katz and Peleg [M. Katz, N.A. Katz, D. Peleg, Distance labeling schemes for well-separated graph classes, Discrete Applied Mathematics 145 (2005) 384-402] by a log n factor.As a byproduct, our data-structure supports all-pair shortest-path queries in O(d) time for distance-d pairs, and so identifies in constant time the first edge along a shortest path between any source and destination.More fundamentally, we show that this optimal space and time data-structure cannot be extended for higher dimension posets. More precisely, we prove that for comparability graphs of three-dimensional posets, every distance labeling scheme requires Ω(n^1/3) bit labels.     

An exact algorithm for MAX-CUT in sparse graphs

We study exact algorithms for the MAX-CUT problem. Introducing a new technique, we present an algorithmic scheme that computes a maximum cut in graphs with bounded maximum degree. Our algorithm runs in time O^*(2^(1-(2/Δ))n). We also describe a MAX-CUT algorithm for general graphs. Its time complexity is O^*(2^mn/(m+n)). Both algorithms use polynomial space.     

On the 2-rainbow domination in graphs

The concept of 2-rainbow domination of a graph G coincides with the ordinary domination of the prism G□K₂. In this paper, we show that the problem of deciding if a graph has a 2-rainbow dominating function of a given weight is NP-complete even when restricted to bipartite graphs or chordal graphs. Exact values of 2-rainbow domination numbers of several classes of graphs are found, and it is shown that for the generalized Petersen graphs GP(n,k) this number is between ⌈4n/5⌉ and n with both bounds being sharp.     

Dynamic programming and planarity: Improved tree-decomposition based algorithms

We study some structural properties for tree-decompositions of 2-connected planar graphs that we use to improve upon the runtime of tree-decomposition based dynamic programming approaches for several NP-hard planar graph problems. E.g., we derive the fastest algorithm for Planar Dominating Set of runtime 3^tw⋅n^O(1), when we take the width tw of a given tree-decomposition as the measure for the exponential worst case behavior. We also introduce a tree-decomposition based approach to solve non-local problems efficiently, such as Planar Hamiltonian Cycle in runtime 6^tw⋅n^O(1). From any input tree-decomposition of a 2-connected planar graph, one computes in time O(nm) a tree-decomposition with geometric properties, which decomposes the plane into disks, and where the graph separators form Jordan curves in the plane.     

Maximum induced matching problem on hhd-free graphs

We show that the maximum induced matching problem can be solved on hhd-free graphs in O(m²) time; hhd-free graphs generalize chordal graphs and the previous best bound was O(m³). Then, we consider a technique used by Brandstädt and Hoàng (2008) [4] to solve the problem on chordal graphs. Extending this, we show that for a subclass of hhd-free graphs that is more general than chordal graphs the problem can be solved in linear time. We also present examples to demonstrate the tightness of our results.     

Fast parallel graph searching with applications

This paper presents fast parallel algorithms for the following graph theoretic problems: breadth-depth search of directed acyclic graphs; minimum-depth search of graphs; finding the minimum-weighted paths between all node-pairs of a weighted graph and the critical activities of an activity-on-edge network. The first algorithm hasO(logdlogn) time complexity withO(n ³) processors and the remaining algorithms achieveO(logd loglogn) time bound withO(n ²[n/loglogn]) processors, whered is the diameter of the graph or the directed acyclic graph (which also represents an activity-on-edge network) withn nodes. These algorithms work on an unbounded shared memory model of the single instruction stream, multiple data stream computer that allows both read and write conflicts.     

Finding a minimum independent dominating set in a permutation graph

We give a linear time reduction of the problem of finding a minimum independent dominating set in a permutation graph, into that of finding a shortest maximal increasing subsequence. We then give an O(n log²n)-time algorithm for solving the second (and hence the first) problem. This improves on the O(n³)-time algorithm given in [4] for solving the problem of finding a minimum independent dominating set in a permutation graph.     

The clique-separator graph for chordal graphs

We present a new representation of a chordal graph called the clique-separator graph, whose nodes are the maximal cliques and minimal vertex separators of the graph. We present structural properties of the clique-separator graph and additional properties when the chordal graph is an interval graph, proper interval graph, or split graph. We also characterize proper interval graphs and split graphs in terms of the clique-separator graph. We present an algorithm that constructs the clique-separator graph of a chordal graph in O(n³) time and of an interval graph in O(n²) time, where n is the number of vertices in the graph.     

An optimal algorithm for finding depth-first spanning tree on permutation graphs

LetG be a connected graph ofn vertices. The problem of finding a depth-first spanning tree ofG is to find a connected subgraph ofG with then vertices andn − 1 edges by depth-first-search. In this paper, we propose anO(n) time algorithm to solve this problem on permutation graphs.     

On a disparity between relative cliquewidth and relative NLC-width

Cliquewidth and NLC-width are two closely related parameters that measure the complexity of graphs. Both clique- and NLC-width are defined to be the minimum number of labels required to create a labelled graph by certain terms of operations. Many hard problems on graphs become solvable in polynomial-time if the inputs are restricted to graphs of bounded clique- or NLC-width. Cliquewidth and NLC-width differ at most by a factor of two.The relative counterparts of these parameters are defined to be the minimum number of labels necessary to create a graph while the tree-structure of the term is fixed. We show that Relative Cliquewidth and Relative NLC-width differ significantly in computational complexity. While the former problem is NP-complete the latter is solvable in polynomial time. The relative NLC-width can be computed in O(n³) time, which also yields an exact algorithm for computing the NLC-width in time O(3ⁿn). Additionally, our technique enables a combinatorial characterisation of NLC-width that avoids the usual operations on labelled graphs.     

An implicit representation of chordal comparability graphs in linear time

Ma and Spinrad have shown that every transitive orientation of a chordal comparability graph is the intersection of four linear orders. That is, chordal comparability graphs are comparability graphs of posets of dimension four. Among other uses, this gives an implicit representation of a chordal comparability graph using O(n) integers so that, given two vertices, it can be determined in O(1) time whether they are adjacent, no matter how dense the graph is. We give a linear time algorithm for finding the four linear orders, improving on their bound of O(n²).     

A fast algorithm for multiplying min-sum permutations

The present article considers the problem for determining, for given two permutations over indices from 1 to n, the permutation whose distribution matrix is identical to the min-sum product of the distribution matrices of the given permutations. This problem has several applications in computing the similarity between strings. The fastest known algorithm to date for solving this problem executes in O(n^1.5) time, or very recently, in O(nlogn) time. The present article independently proposes another O(nlogn)-time algorithm for the same problem, which can also be used to partially solve the problem efficiently with respect to time in the sense that, for given indices g and i with 1≤g<i≤n+1, the proposed algorithm outputs the values R(h) for all indices h with g≤h<i in O(n+(i−g)log(i−g)) time, where R is the solution of the problem.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.