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

Ju-Yuan Hsiao, Chuan Yi Tang, Ruay Shiung Chang

Research output: Contribution to journalArticle

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 languageEnglish
Pages (from-to)283-287
Number of pages5
JournalInformation Processing Letters
Volume40
Issue number5
DOIs
Publication statusPublished - 1991 Dec 13

Fingerprint

Graph Searching
Independent Set
Graph in graph theory

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this

@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 = "Ju-Yuan Hsiao 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",

}

Solving the single step graph searching problem by solving the maximum two-independent set problem. / Hsiao, Ju-Yuan; Tang, Chuan Yi; Chang, Ruay Shiung.

In: Information Processing Letters, Vol. 40, No. 5, 13.12.1991, p. 283-287.

Research output: Contribution to journalArticle

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 -