Computer Science and Engineering
10.17.50.243//handle/2074/7896
Tue, 26 Sep 2023 10:41:28 GMT2023-09-26T10:41:28ZPlanar graph coloring is not self-reducible, assuming P ≠ NP
10.17.50.243//handle/12345678/2507
Planar graph coloring is not self-reducible, assuming P ≠ NP
Vazirani, Vijay V; Khuller, Samir
We show that obtaining the lexicographically first four coloring of a planar graph is NP-hard. This shows that planar graph four-coloring is not self-reducible, assuming P≠ NP. One consequence of our result is that the schema of Jerrum et al. (1986) cannot be used for approximately counting the number of four colorings of a planar graph. These results extend to planar graph k-coloring, for k4.
Tue, 01 Jan 1991 00:00:00 GMT10.17.50.243//handle/12345678/25071991-01-01T00:00:00ZFinding nonfaulty subtrees in faulty binary tree architectures
10.17.50.243//handle/12345678/2420
Finding nonfaulty subtrees in faulty binary tree architectures
Mittal, Ravi; Jain, Bijendra N; Patney, Rakesh K
In this paper we have studied fault tolerance of a full binary tree in terms of availability of non-faulty (full) subtrees. When an unaugmented full binary tree is faulty, then the computation can be carried out on the largest available non-faulty (full) binary subtree.
It is shown that the minimum number of faulty nodes required to destroy all subtrees of height h in a full binary tree of height n is given as fbt(n, h) = (2n−1)/(2h−1). It follows that the availability of a non-faulty subtree of height h = n−w, in an n level full binary tree containing u faulty nodes, can be ensured, where w is the smallest integer such that u ≤ 2w.
An algorithm which evaluates whether a given set of faulty nodes will destroy all subtrees of some specified height, is given. This algorithm can also evaluate the largest available non-faulty subtree in a faulty full binary tree. We also study the availability of a non-faulty subtree in some augmented binary tree architectures.
Sat, 01 Jan 1994 00:00:00 GMT10.17.50.243//handle/12345678/24201994-01-01T00:00:00ZImproved bounds for the max-flow min-multicut ratio for planar and Kr, r-free graphs
10.17.50.243//handle/12345678/2405
Improved bounds for the max-flow min-multicut ratio for planar and Kr, r-free graphs
Tardos, Éva; Vazirani, Vijay V
We consider the version of the multicommodity flow problem in which the objective is to maximize the sum of commodities routed. Garg, Vazirani and Yannakakis proved that the minimum multicut and maximum flow ratio for this problem can be bounded by O(log k), where k is the number of commodities. In this note we improve this ratio to O(1) for planar graphs, and more generally to O(r3) for graphs with an excluded Kr, r minor. The proof is based on the network decomposition theorem of Klein, Plotkin and Rao. Our proof is constructive and yields approximation algorithms, with the same factors, for the minimum multicut problem on such networks.
Fri, 01 Jan 1993 00:00:00 GMT10.17.50.243//handle/12345678/24051993-01-01T00:00:00ZOn-line algorithms for weighted bipartite matching and stable marriages
10.17.50.243//handle/12345678/2347
On-line algorithms for weighted bipartite matching and stable marriages
Khuller, Samir; Mitchell, Stephen G; Vazirani, Vijay V
We give an on-line deterministic algorithm for the weighted bipartite matching problem that achieves a competitive ratio of (2n−1) in any metric space (where n is the number of vertices). This algorithm is optimal - there is no on-line deterministic algorithm that achieves a competitive ratio better than (2n−1) in all metric spaces.
We also study the stable marriage problem, where we are interested in the number of unstable pairs produced. We show that the simple “first come, first served” deterministic algorithm yields on the average O(n log n) unstable pairs, but in the worst case no deterministic or randomized on-line algorithm can do better than ω(n2) unstable pairs. This appears to be the first on-line problem for which provably one cannot do better with randomization; for most on-line problems studied in the past, randomization has helped in improving the performance.
Sat, 01 Jan 1994 00:00:00 GMT10.17.50.243//handle/12345678/23471994-01-01T00:00:00Z