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

Page 1

Displaying 1 – 13 of 13

Showing per page

Parallel Algorithms for Maximal Cliques in Circle Graphs and Unrestricted Depth Search

E. N. Cáceres, S. W. Song, J. L. Szwarcfiter (2010)

RAIRO - Theoretical Informatics and Applications

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of...

Partial covers of graphs

Jirí Fiala, Jan Kratochvíl (2002)

Discussiones Mathematicae Graph Theory

Given graphs G and H, a mapping f:V(G) → V(H) is a homomorphism if (f(u),f(v)) is an edge of H for every edge (u,v) of G. In this paper, we initiate the study of computational complexity of locally injective homomorphisms called partial covers of graphs. We motivate the study of partial covers by showing a correspondence to generalized (2,1)-colorings of graphs, the notion stemming from a practical problem of assigning frequencies to transmitters without interference. We compare the problems of...

Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases

E. Bampis, A. Giannakos, A. Karzanov, Y. Manoussakis, I. Milis (2010)

RAIRO - Theoretical Informatics and Applications

It is known that finding a perfect matching in a general graph is AC0-equivalent to finding a perfect matching in a 3-regular (i.e. cubic) graph. In this paper we extend this result to both, planar and bipartite cases. In particular we prove that the construction problem for perfect matchings in planar graphs is as difficult as in the case of planar cubic graphs like it is known to be the case for the famous Map Four-Coloring problem. Moreover we prove that the existence and construction...

Perfectly matchable subgraph problem on a bipartite graph

Firdovsi Sharifov (2010)

RAIRO - Operations Research

We consider the maximum weight perfectly matchable subgraph problem on a bipartite graph G=(UV,E) with respect to given nonnegative weights of its edges. We show that G has a perfect matching if and only if some vector indexed by the nodes in UV is a base of an extended polymatroid associated with a submodular function defined on the subsets of UV. The dual problem of the separation problem for the extended polymatroid is transformed to the special maximum flow problem on G. In this paper, we give...

Polynomial time algorithms for two classes of subgraph problem

Sriraman Sridharan (2008)

RAIRO - Operations Research

We design a O(n3) polynomial time algorithm for finding a (k-1)- regular subgraph in a k-regular graph without any induced star K1,3(claw-free). A polynomial time algorithm for finding a cubic subgraph in a 4-regular locally connected graph is also given. A family of k-regular graphs with an induced star K1,3 (k even, k ≥ 6), not containing any (k-1)-regular subgraph is also constructed.

Primal-dual approximation algorithms for a packing-covering pair of problems

Sofia Kovaleva, Frits C. R. Spieksma (2002)

RAIRO - Operations Research - Recherche Opérationnelle

We consider a special packing-covering pair of problems. The packing problem is a natural generalization of finding a (weighted) maximum independent set in an interval graph, the covering problem generalizes the problem of finding a (weighted) minimum clique cover in an interval graph. The problem pair involves weights and capacities; we consider the case of unit weights and the case of unit capacities. In each case we describe a simple algorithm that outputs a solution to the packing problem and...

Primal-dual approximation algorithms for a packing-covering pair of problems

Sofia Kovaleva, Frits C.R. Spieksma (2010)

RAIRO - Operations Research

We consider a special packing-covering pair of problems. The packing problem is a natural generalization of finding a (weighted) maximum independent set in an interval graph, the covering problem generalizes the problem of finding a (weighted) minimum clique cover in an interval graph. The problem pair involves weights and capacities; we consider the case of unit weights and the case of unit capacities. In each case we describe a simple algorithm that outputs a solution to the packing problem and...

Currently displaying 1 – 13 of 13

Page 1