The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
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...
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...
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...
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...
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.
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...
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