Browsing by Author "Narasimhan, Giri"
Now showing items 1-5 of 5
-
Algorithms for the Maximum Induced Bipartite Subgraph Problem on Interval and Circular-Arc Graphs
Manber, Rachel; Narasimhan, Giri (University of Wisconsin-Madison Department of Computer Sciences, 1987) -
A Generalization of Lovasz's Sandwich Theorem
Narasimhan, Giri; Manber, Rachel (University of Wisconsin-Madison Department of Computer Sciences, 1988) -
The Maximum K-Colorable Subgraph Problem
Narasimhan, Giri (University of Wisconsin-Madison Department of Computer Sciences, 1989)For a given graph, the Maximum k-Colorable Subgraph Problem is the problem of determining the largest set of vertices of the graph that can be colored using k distinct colors such that adjacent vertices, if colored, are ... -
A Note on the Hamiltonian Circuit Problem on Directed Path Graphs
Narasimhan, Giri (University of Wisconsin-Madison Department of Computer Sciences, 1989)Bertossi and Bonuccelli [2] proved that the Hamiltonian Circuit problem in NP-Complete even when the inputs are restricted to the special class of Undirected Path graphs. The corresponding problem on Directed Path graphs ... -
Stability Number and Chromatic Number of Tolerance Graphs
Narasimhan, Giri; Manber, Rachel (University of Wisconsin-Madison Department of Computer Sciences, 1988)