Extending planar graph algorithms to K 3,3-free graphs

Samir Khuller*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

For several problems, restricting attention to special classes of graphs has yielded better algorithms. In particular, restricting to planar graphs yields efficient parallel algorithms for several graph problems. In this paper we extend these algorithms to K3,3-free graphs, showing that the restriction of planarity is not important. The three problems dealt with are : graph coloring, depth first search and maximal independent sets. As a corollary we show that K3,3-free graphs are five colorable (this bound is tight).

Original languageEnglish (US)
Title of host publicationFoundations of Software Technology and Theoretical Computer Science - 8th Conference, Proceedings
EditorsKesav V. Nori, Sanjeev Kumar
PublisherSpringer Verlag
Pages67-79
Number of pages13
ISBN (Print)9783540505174
DOIs
StatePublished - 1988
Event8th International Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1988 - Pune, India
Duration: Dec 21 1988Dec 23 1988

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume338 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference8th International Conference on Foundations of Software Technology and Theoretical Computer Science, FST and TCS 1988
Country/TerritoryIndia
CityPune
Period12/21/8812/23/88

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Extending planar graph algorithms to K <sub>3,3</sub>-free graphs'. Together they form a unique fingerprint.

Cite this