Serial and Parallel Algorithms for (k,2)-Partite Graphs

✍ Scribed by J.A. Ellis; M. Matamontero; H. Muller

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 693 KB
• Volume: 22
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1994.1076

✦ Synopsis

We introduce a class of layered graphs which we call ((k, 2)) partite and which we argue are an interesting class because of several important applications. We show that testing for ((k, 2)) partiteness can be done efficiently both on sequential and parallel machines, by showing that membership is in (\operatorname{NSPACE}(\log n)) and in (N C^{2}). We show that ((k, 2))-partite graphs have bounded path width. We then show that a particular NP-complete problem, namely Maximum Independent Set, is solvable in linear time on bounded pathwidth graphs if the path decomposition is included in the input. Finally, we show that the Maximum Independent Set problem is in (N C^{2}) for ( (k, 2) )-partite graphs. We note that linear time solutions for certain NP-complete problems have been shown for a wider class of graphs, namely partial (k)-trees. Our linear time algorithm is somewhat simpler in structure. We conjecture that our techniques can be used on many NP-complete problems to yield efficient algorithms for ((k, 2))-partite graphs. O 1994 Academic Press. Inc.