Hamilton decompositions and -factorizations of hypercubes.
Homomorphism duality for rooted oriented paths
Let be a fixed rooted digraph. The -coloring problem is the problem of deciding for which rooted digraphs there is a homomorphism which maps the vertex to the vertex . Let be a rooted oriented path. In this case we characterize the nonexistence of such a homomorphism by the existence of a rooted oriented cycle , which is homomorphic to but not homomorphic to . Such a property of the digraph is called rooted cycle duality or -cycle duality. This extends the analogical result for...
How to find overfull subgraphs in graphs with large maximum degree. II.
Implementation of directed acyclic word graph
An effective implementation of a Directed Acyclic Word Graph (DAWG) automaton is shown. A DAWG for a text is a minimal automaton that accepts all substrings of a text , so it represents a complete index of the text. While all usual implementations of DAWG needed about 30 times larger storage space than was the size of the text, here we show an implementation that decreases this requirement down to four times the size of the text. The method uses a compression of DAWG elements, i. e. vertices,...
INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs
Induced Acyclic Tournaments in Random Digraphs: Sharp Concentration, Thresholds and Algorithms
Given a simple directed graph D = (V,A), let the size of the largest induced acyclic tournament be denoted by mat(D). Let D ∈ D(n, p) (with p = p(n)) be a random instance, obtained by randomly orienting each edge of a random graph drawn from Ϟ(n, 2p). We show that mat(D) is asymptotically almost surely (a.a.s.) one of only 2 possible values, namely either b*or b* + 1, where b* = ⌊2(logrn) + 0.5⌋ and r = p−1. It is also shown that if, asymptotically, 2(logrn) + 1 is not within a distance of w(n)/(ln...
Interchangeability of relevant cycles in graphs.
Interval Incidence Coloring of Subcubic Graphs
In this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is NP-complete, and they asked if Xii(G) ≤ 2Δ(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with Δ(G) = 3.
I/O-optimal algorithms for outerplanar graphs.
Labeled shortest paths in digraphs with negative and positive edge weights
This paper gives a shortest path algorithm for CFG (context free grammar) labeled and weighted digraphs where edge weights may be positive or negative, but negative-weight cycles are not allowed in the underlying unlabeled graph. These results build directly on an algorithm of Barrett et al. [SIAM J. Comput.30 (2000) 809–837]. In addition to many other results, they gave a shortest path algorithm for CFG labeled and weighted digraphs where all edges are nonnegative. Our algorithm is based closely...
Level planar embedding in linear time.
Linear programming and the worst-case analysis of greedy algorithms on cubic graphs.
Linear time recognition of -indifference graphs.
Listing all plane graphs.
Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring.
Lower bounds for the number of bends in three-dimensional orthogonal graph drawings.
Marginalization in models generated by compositional expressions
In the framework of models generated by compositional expressions, we solve two topical marginalization problems (namely, the single-marginal problem and the marginal-representation problem) that were solved only for the special class of the so-called “canonical expressions”. We also show that the two problems can be solved “from scratch” with preliminary symbolic computation.
Maximal buttonings of trees
A buttoning of a tree that has vertices v1, v2, . . . , vn is a closed walk that starts at v1 and travels along the shortest path in the tree to v2, and then along the shortest path to v3, and so forth, finishing with the shortest path from vn to v1. Inspired by a problem about buttoning a shirt inefficiently, we determine the maximum length of buttonings of trees
Maximum Semi-Matching Problem in Bipartite Graphs
An (f, g)-semi-matching in a bipartite graph G = (U ∪ V,E) is a set of edges M ⊆ E such that each vertex u ∈ U is incident with at most f(u) edges of M, and each vertex v ∈ V is incident with at most g(v) edges of M. In this paper we give an algorithm that for a graph with n vertices and m edges, n ≤ m, constructs a maximum (f, g)-semi-matching in running time O(m ⋅ min [...] ) Using the reduction of [5] our result on maximum (f, g)-semi-matching problem directly implies an algorithm for the optimal...
Memory paging for connectivity and path problems in graphs.