Results 61 to 70 of about 104 (103)
A simple algorithm for constructing Szemerédi's Regularity Partition
, 1999 We give a simple constructive version of Szemer'edi's Regularity Lemma, based on the computation of singular values of matrices. Mathematical Reviews Subject Numbers: 05C85, 68R10.
Alan Frieze, Ravi Kannan
core
Dominating Sets Whose Closed Stars Form Spanning Trees
, 1995 For a subset W of vertices of an undirected graph G, let S(W ) be the subgraph consisting of W , all edges incident to at least one vertex in W , and all vertices adjacent to at least one vertex in W .
Jerrold W. Grossman
core
Optimizing Bull-Free Perfect Graphs
, 1997 . A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. Here we present polynomial-time combinatorial algorithms for the optimal weighted coloring and weighted clique problems in bull-free perfect graphs. The algorithms are
Celina M. H. De Figueiredo +1 more
core
We study formal path expressions for two edge-labeled two-terminal directed acyclic graph families: directed triangulated grid graphs (TGGs) and directed king graphs.
Vadim E. Levit, Mark Korenblit
core +1 more source
Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
, 1996 This paper develops new techniques for constructing separators for graphs embedded on surfaces of bounded genus. For any arbitrarily small positive " we show that any n-vertex graph G of genus g can be divided in O(n + g) time into components whose ...
L. Aleksandrov, H. Djidjev
core
Local Conditions for Edge-Coloring
, 1995 In this note, we investigate three versions of the overfull property for graphs and their relation to the edge-coloring problem. Each of these properties implies that the graph cannot be edge-colored with \Delta colors, where \Delta is the maximum degree.
Celina M. H. De Figueiredo +2 more
core
On the quality of spectral separators
, 1998 . Computing graph separators is an important step in many graph algorithms. A popular technique for finding separators involves spectral methods. However, there has not been much prior analysis of the quality of the separators produced by this technique;
Gary, L. Miller, Stephen Guattery
core
Finding All Maximal Cliques of a Family of Induced Subgraphs
, 2008 Many real world problems can be mapped onto graphs and solved with well-established efficient algorithms studied in graph theory. One such problem is the following: given a set of objects and an irreflexive and symmetric relation between these objects ...
Daniel Baum
core
Novel procedures for graph edge-colouring
, 2018 Orientador: Dr. Renato CarmoCoorientador: Dr. André Luiz Pires GuedesTese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática.
Zatesko, Leandro Miranda, 1988-
core
The Page Number Problem for Partially Ordered Sets
, 2013 Umieszczenie grafu w książce jest definiowane przez kolejność jego wierzchołków na grzbiecie książki i przyporządkowanie jego krawędzi stronom książki tak, aby na żadnej stronie krawędzie nie przecinały się. Umieszczenie zbioru częściowo uporządkowanego (
Kwiatkowska, Anna Beata
core