Consequences of an algorithm for bridged graphs

Chepoi showed that every breadth first search of a bridged graph produces a cop-win ordering of the graph. We note here that Chepoi's proof gives a simple proof of the theorem that G is bridged if and only if G is cop-win and has no induced cycle of length four or five, and that this characterization together with Chepoi's proof reduces the time complexity of bridged graph recognition. Specifically, we show that bridged graph recognition is equivalent to (C₄,C₅)-free graph recognition, and reduce the best known time complexity from O(n⁴) to O(n^3.376).     

Cycle-free partial orders and chordal comparability graphs

This paper studies a number of problems on cycle-free partial orders and chordal comparability graphs. The dimension of a cycle-free partial order is shown to be at most 4. A linear time algorithm is presented for determining whether a chordal directed graph is transitive, which yields an O(n ²) algorithm for recognizing chordal comparability graphs. An algorithm is presented for determining whether the transitive closure of a digraph is a cycle-free partial order in O(n+m _t)time, where m _tis the number of edges in the transitive closure.     

An improved edge bound on the interval number of a graph

The upper bound on the interval number of a graph in terms of its number of edges is improved. Also, the interval number of graphs in hereditary classes is bounded in terms of the vertex degrees.     

Edge subdivision and dimension

The dimension of a partial order can be multiplied by an arbitrarily large factor when edges are subdivided.This research was supported by National Science Foundation grant DCR-8604577.     

Finding a Sun in Building-Free Graphs

Deciding whether an arbitrary graph contains a sun was recently shown to be NP-complete (Hoàng in SIAM J Discret Math 23:2156–2162, 2010). We show that whether a building-free graph contains a sun can be decided in O(min{mn ³, m ^1.5 n ²}) time and, if a sun exists, it can be found in the same time bound. The class of building-free graphs contains many interesting classes of perfect graphs such as Meyniel graphs which, in turn, contains classes such as hhd-free graphs, i-triangulated graphs, and parity graphs. Moreover, there are imperfect graphs that are building-free. The class of building-free graphs generalizes several classes of graphs for which an efficient test for the presence of a sun is known. We also present a vertex elimination scheme for the class of (building, gem)-free graphs. The class of (building, gem)-free graphs is a generalization of the class of distance hereditary graphs and a restriction of the class of (building, sun)-free graphs.     

Worst case analysis of a graph coloring algorithm

In this paper, we show that a graph coloring heuristic developed by Brélaz may use n colors to color a 3-colorable graph with O(n) vertices.     

Transitive closure for restricted classes of partial orders

Most papers dealing with partial orders assume that the input is given either in transitively closed or transitively reduced form. In this paper, we show that it is possible to solve some problems on partial orders in less time than it takes to perform transitive closure or reduction for general graphs. In particular, we present efficient algorithms for recognizing two dimensional partial orders and N-free partial orders when no assumptions are made about the form of the input.This work was supported by National Science Foundation Grant DCR-8604577 and the Vanderbilt University Research Council.     

Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number

Partially ordered sets of small width and graphs of small Dilworth number have many interesting properties and have been well studied. Here we show that recognition of such orders and graphs can be done more efficiently than by using the well-known algorithms based on bipartite matching and matrix multiplication. In particular, we show that deciding deciding if an order has width k can be done in O(kn ²) time and whether a graph has Dilworth number k can be done in O(k ² n ²) time.For very small k we have even better results. We show that orders of width at most 3 can be recognized in O(n) time and of width at most 4 in O(nlog n).     

Worst-case analysis of a scheduling algorithm

In this note, a heuristic proposed by Ibarra and Kim (IK) for scheduling independent tasks on unrelated processors is analyzed. The heuristic may create a schedule which finishes a time $\text{m 1 OPT}$, where m is the number of processors, and OPT is the time used in the optimal schedule. This compares unfavorably with the heuristics described by Davis and Jaffe [2], which have worst-case behavior which is $\text{O(OPT 1 m}{}^{0.5}\text{)}$.     

Domination graphs: examples and counterexamples

We give a counterexample to a conjecture of Dahlhaus et al. [3] claiming that the Special Quadratic Consensus Method yields a polynomial-time recognition for domination graphs, and discuss several new properties of domination graphs.