All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 23 Next

Displaying 441 – 460 of 5365

Showing per page

A sparse dynamic programming algorithm for alignment with non-overlapping inversions

Alair Pereira do Lago, Ilya Muchnik, Casimir Kulikowski (2010)

RAIRO - Theoretical Informatics and Applications

Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions is...

A spectral bound for graph irregularity

Felix Goldberg (2015)

Czechoslovak Mathematical Journal

The imbalance of an edge e = { u , v } in a graph is defined as i ( e ) = | d ( u ) - d ( v ) | , where d ( · ) is the vertex degree. The irregularity I ( G ) of G is then defined as the sum of imbalances over all edges of G . This concept was introduced by Albertson who proved that I ( G ) ≤ 4 n 3 / 27 (where n = | V ( G ) | ) and obtained stronger bounds for bipartite and triangle-free graphs. Since then a number of additional bounds were given by various authors. In this paper we prove a new upper bound, which improves a bound found by Zhou and Luo in 2008. Our bound involves the...

A stationary random graph of no growth rate

Ádám Timár (2014)

Annales de l'I.H.P. Probabilités et statistiques

We present a random automorphism-invariant subgraph of a Cayley graph such that with probability 1 its exponential growth rate does not exist.

A strongly non-Ramsey uncountable graph

Péter Komjáth (1997)

Fundamenta Mathematicae

It is consistent that there exists a graph X of cardinality ℵ 1 such that every graph has an edge coloring with ℵ 1 colors in which the induced copies of X (if there are any) are totally multicolored (get all possible colors).

A sufficient condition for the existence of k-kernels in digraphs

H. Galeana-Sánchez, H.A. Rincón-Mejía (1998)

Discussiones Mathematicae Graph Theory

In this paper, we prove the following sufficient condition for the existence of k-kernels in digraphs: Let D be a digraph whose asymmetrical part is strongly conneted and such that every directed triangle has at least two symmetrical arcs. If every directed cycle γ of D with l(γ) ≢ 0 (mod k), k ≥ 2 satisfies at least one of the following properties: (a) γ has two symmetrical arcs, (b) γ has four short chords. Then D has a k-kernel. This result generalizes some previous results...

A survey of hereditary properties of graphs

Mieczysław Borowiecki, Izak Broere, Marietjie Frick, Peter Mihók, Gabriel Semanišin (1997)

Discussiones Mathematicae Graph Theory

In this paper we survey results and open problems on the structure of additive and hereditary properties of graphs. The important role of vertex partition problems, in particular the existence of uniquely partitionable graphs and reducible properties of graphs in this structure is emphasized. Many related topics, including questions on the complexity of related problems, are investigated.

A Survey of the Path Partition Conjecture

Marietjie Frick (2013)

Discussiones Mathematicae Graph Theory

The Path Partition Conjecture (PPC) states that if G is any graph and (λ1, λ2) any pair of positive integers such that G has no path with more than λ1 + λ2 vertices, then there exists a partition (V1, V2) of the vertex set of G such that Vi has no path with more than λi vertices, i = 1, 2. We present a brief history of the PPC, discuss its relation to other conjectures and survey results on the PPC that have appeared in the literature since its first formulation in 1981.

A survey on combinatorial optimization in dynamic environments∗

Nicolas Boria, Vangelis T. Paschos (2011)

RAIRO - Operations Research

This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...

Currently displaying 441 – 460 of 5365