Extending planar graph algorithms to K3,3-free graphs

Samir Khuller

doi:10.1016/0890-5401(90)90031-C

Extending planar graph algorithms to K_3,3-free graphs

Samir Khuller^*

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

7 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 K_3,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 K_3,3-free graphs are five colorable (this bound is tight).

Original language	English (US)
Pages (from-to)	13-25
Number of pages	13
Journal	Information and Computation
Volume	84
Issue number	1
DOIs	https://doi.org/10.1016/0890-5401(90)90031-C
State	Published - Jan 1990

ASJC Scopus subject areas

Theoretical Computer Science
Information Systems
Computer Science Applications
Computational Theory and Mathematics

Access to Document

10.1016/0890-5401(90)90031-C

Cite this

@article{8ebcdb6728344a7d96402a73a4a04ef3,

title = "Extending planar graph algorithms to K3,3-free graphs",

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).",

author = "Samir Khuller",

note = "Funding Information: by NSF Grant DCR 85-52938 and PYI matching funds from AT & T Bell",

year = "1990",

month = jan,

doi = "10.1016/0890-5401(90)90031-C",

language = "English (US)",

volume = "84",

pages = "13--25",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - Extending planar graph algorithms to K3,3-free graphs

AU - Khuller, Samir

N1 - Funding Information: by NSF Grant DCR 85-52938 and PYI matching funds from AT & T Bell

PY - 1990/1

Y1 - 1990/1

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=0025223920&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025223920&partnerID=8YFLogxK

U2 - 10.1016/0890-5401(90)90031-C

DO - 10.1016/0890-5401(90)90031-C

M3 - Article

AN - SCOPUS:0025223920

SN - 0890-5401

VL - 84

SP - 13

EP - 25

JO - Information and Computation

JF - Information and Computation

IS - 1

ER -

Extending planar graph algorithms to K_3,3-free graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this