Solving the single step graph searching problem by solving the maximum two-independent set problem

Ju Yuan Hsiao; Chuan Yi Tang; Ruay Shiung Chang

doi:10.1016/0020-0190(91)90124-Z

Solving the single step graph searching problem by solving the maximum two-independent set problem

Ju Yuan Hsiao, Chuan Yi Tang, Ruay Shiung Chang

Department of Computer Science and Information Engineering

Research output: Contribution to journal › Article

8 Citations (Scopus)

Abstract

The problem of single step searching a graph is investigated. We show that this problem can be solved by solving the maximum two-independent set problem. Results about solving the single step graph searching problem on special graphs are listed.

Original language	English
Pages (from-to)	283-287
Number of pages	5
Journal	Information Processing Letters
Volume	40
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(91)90124-Z
Publication status	Published - 1991 Dec 13

Fingerprint

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Cite this

Hsiao, J. Y., Tang, C. Y., & Chang, R. S. (1991). Solving the single step graph searching problem by solving the maximum two-independent set problem. Information Processing Letters, 40(5), 283-287. https://doi.org/10.1016/0020-0190(91)90124-Z

@article{b2fdd46af64d41e2a5565b262fa99f2e,

title = "Solving the single step graph searching problem by solving the maximum two-independent set problem",

abstract = "The problem of single step searching a graph is investigated. We show that this problem can be solved by solving the maximum two-independent set problem. Results about solving the single step graph searching problem on special graphs are listed.",

author = "Hsiao, {Ju Yuan} and Tang, {Chuan Yi} and Chang, {Ruay Shiung}",

year = "1991",

month = "12",

day = "13",

doi = "10.1016/0020-0190(91)90124-Z",

language = "English",

volume = "40",

pages = "283--287",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - Solving the single step graph searching problem by solving the maximum two-independent set problem

AU - Hsiao, Ju Yuan

AU - Tang, Chuan Yi

AU - Chang, Ruay Shiung

PY - 1991/12/13

Y1 - 1991/12/13

N2 - The problem of single step searching a graph is investigated. We show that this problem can be solved by solving the maximum two-independent set problem. Results about solving the single step graph searching problem on special graphs are listed.

AB - The problem of single step searching a graph is investigated. We show that this problem can be solved by solving the maximum two-independent set problem. Results about solving the single step graph searching problem on special graphs are listed.

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

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

U2 - 10.1016/0020-0190(91)90124-Z

DO - 10.1016/0020-0190(91)90124-Z

M3 - Article

AN - SCOPUS:0026297104

VL - 40

SP - 283

EP - 287

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 5

ER -

Access to Document

10.1016/0020-0190(91)90124-Z