On the Structure of Contractible Vertex Pairs in Chordal Graphs
An edge/non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. We focus our study on contractible edges and non-edges in chordal graphs. Firstly, we characterize contractible edges in chordal graphs using properties of tree decompositions with respect to minimal vertex separators. Secondly, we show that in every chordal graph each non-edge is contractible. We also characterize non-edges whose contraction leaves a k-connected chordal graph. © 2009 Elsevier B.V. All rights reserved.
On the arrangement of cliques in chordal graphs with respect to the cuts
A cut (A, B) (where B = V - A) in a graph G(V, E) is called internal, iff there exists a node x in A which is not adjacent to any node in B and there exists a node y ε B such that it is not adjacent to any node in A. In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut (A, B) in a chordal graph G, there exists a clique with κ(G) + 1 nodes (where κ(G) is the vertex connectivity of G) such that it is (approximately) bisected by the cut (A, B). In fact we give a stronger result: For any internal cut (A, B) of a chordal graph, for each i, 0 ≤ i ≤ κ(G) + 1, there exists a clique Ki such that |Ki| = κ(G) + 1, |A ∩ Ki| = i and |B ∩ Ki| = κ(G) + 1 - i. An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be Ω(k2), where κ(G) = k. Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least κ(G)(κ(G)+1)/2, where κ(G) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to κ(G). This result is tight. © Springer-Verlag Berlin Heidelberg 2004.
A new characterization of matrices with the consecutive ones property
We consider the following constraint satisfaction problem: Given a set F of subsets of a finite set S of cardinality n, and an assignment of intervals of the discrete set {1, ..., n} to each of the subsets, does there exist a bijection f : S → {1, ..., n} such that for each element of F, its image under f is same as the interval assigned to it. An interval assignment to a given set of subsets is called feasible if there exists such a bijection. In this paper, we characterize feasible interval assignments to a given set of subsets. We then use this result to characterize matrices with the Consecutive Ones Property (COP), and to characterize matrices for which there is a permutation of the rows such that the columns are all sorted in ascending order. We also present a characterization of set systems which have a feasible interval assignment. © 2009 Elsevier B.V. All rights reserved.
On the arrangement of cliques in Chordal graphs with respect to the cuts
A cut (A, B) (where B = V - A) in a graph G = (V, B) is called internal if and only if there exists a vertex x in A that is not adjacent to any vertex in B and there exists a vertex y ε B such that it is not adjacent to any vertex in A. In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut (A, B) in a chordal graph G, there exists a clique with κ(G) + 1 vertices (where κ(G) is the vertex connectivity of G) such that it is (approximately) bisected by the cut (A, B). In fact we give a stronger result: For any internal cut (A, B) of a chordal graph, and for each i, 0 ≤ i ≤ κ(G) + 1, there exists a clique Ki such that \K 2\ = κ(G) + 1, \A ∪ K,\ = i and \B ∪ K2\ = κ(G) + l-i. An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be ω(k 2), where κ(G) = k. Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least κ(G)(κ(G)+1)/2 where κ(G) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to κ(G). This result is tight.
Algorithms for satisfiability using independent sets of variables
An independent set of variables is one in which no two variables occur in the same clause in a given instance of k-SAT. Instances of k-SAT with an independent set of size i can be solved in time, within a polynomial factor of 2n-i. In this paper, we present an algorithm for k-SAT based on a modification of the Satisfiability Coding Lemma. Our algorithm runs within a polynomial factor of 2(n-i)(1-1/2k-2), where i is the size of an independent set. We also present a variant of Schöning's randomized local-search algorithm for k-SAT that runs in time which is with in a polynomial factor of (2k-3/k-1)n-i. © Springer-Verlag Berlin Heidelberg 2005.
Analysis of algorithms for an online version of the convoy movement problem
In the convoy movement problem (CMP), a set of convoys must be routed from specified origins to destinations in a transportation network, represented by an undirected graph. Two convoys may not cross each other on the same edge while travelling in opposing directions, a restriction referred to as blocking. However, convoys are permitted to follow each other on the same edge, with a specified headway separating them, but no overtaking is permitted. Further, the convoys to be routed are distinguished based on their length. Particle convoys have zero length and are permitted to traverse an edge simultaneously, whereas convoys with non-zero length have to follow each other, observing a headway. The objective is to minimize the total time taken by convoys to travel from their origins to their destinations, given the travel constraints on the edges. We consider an online version of the CMP where convoy demands arise dynamically over time. For the special case of particle convoys, we present an algorithm that has a competitive ratio of 3 in the worst case and (5/2) on average. For the particle convoy problem, we also present an alternate, randomized algorithm that provides a competitive ratio of (√ 13-1). We then extend the results to the case of convoys with length, which leads to an algorithm with an O(TCL) competitive ratio, where T={Maxet(e)}/{Minet(e)}, C is the maximum congestion (the number of distinct convoy origin-destination pairs that use any edge e) and L={MaxcL(c)}/{MincL(c)}; here L(c)>0 represents the time-headway to be observed by any convoy that follows c and t(e) represents the travel time for a convoy c on edge e. © 2009 Operational Research Society Ltd.
On the structure of contractible edges in k-connected partial k-trees
Contraction of an edge e merges its end points into a new single vertex, and each neighbor of one of the end points of e is a neighbor of the new vertex. An edge in a k-connected graph is contractible if its contraction does not result in a graph with lesser connectivity; otherwise the edge is called non-contractible. In this paper, we present results on the structure of contractible edges in k-trees and k-connected partial k-trees. Firstly, we show that an edge e in a k-tree is contractible if and only if e belongs to exactly one (k + 1) clique. We use this characterization to show that the graph formed by contractible edges is a 2-connected graph. We also show that there are at least {pipe}V(G){pipe} + k - 2 contractible edges in a k-tree. Secondly, we show that if an edge e in a partial k-tree is contractible then e is contractible in any k-tree which contains the partial k-tree as an edge subgraph. We also construct a class of contraction critical 2k-connected partial 2k-trees. © 2009 Springer.
Sequences characterizing k-Trees
A non-decreasing sequence of n integers is the degree sequence of a 1-tree (i.e., an ordinary tree) on n vertices if and only if there are least two 1's in the sequence, and the sum of the elements is 2(n - 1). We generalize this result in the following ways. First, a natural generalization of this statement is a necessary condition for k-trees, and we show that it is not sufficient for any k > 1. Second, we identify non-trivial sufficient conditions for the degree sequences of 2-trees. We also show that these sufficient conditions are almost necessary using bounds on the partition function p(n) and probabilistic methods. Third, we generalize the characterization of degrees of 1-trees in an elegant and counter-intuitive way to yield integer sequences that characterize k-trees, for all k. © Springer-Verlag Berlin Heidelberg 2006.
A note on the Hadwiger number of circular arc graphs
The intention of this note is to motivate the researchers to study Hadwiger's conjecture for circular arc graphs. Let η (G) denote the largest clique minor of a graph G, and let χ (G) denote its chromatic number. Hadwiger's conjecture states that η (G) ≥ χ (G) and is one of the most important and difficult open problems in graph theory. From the point of view of researchers who are sceptical of the validity of the conjecture, it is interesting to study the conjecture for graph classes where η (G) is guaranteed not to grow too fast with respect to χ (G), since such classes of graphs are indeed a reasonable place to look for possible counterexamples. We show that in any circular arc graph G, η (G) ≤ 2 χ (G) - 1, and there is a family with equality. So, it makes sense to study Hadwiger's conjecture for this family. © 2007 Elsevier B.V. All rights reserved.
An improved algorithm for online coloring of intervals with bandwidth
We present an improved online algorithm for coloring interval graphs with bandwidth. This problem has recently been studied by Adamy and Erlebach and a 195-competitive online strategy has been presented. We improve this by presenting a 10-competitive strategy. To achieve this result, we use variants of an optimal online coloring algorithm due to Kierstead and Trotter. © 2006 Elsevier B.V. All rights reserved.