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

DOI10.1016/0020-0190(91)90124-ZzbMath0743.68109OpenAlexW1979977220MaRDI QIDQ1183488

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

Publication date: 28 June 1992

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90124-z

zbMATH Keywords

graph searching problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Single step searching in weighted block graphs ⋮ A sequential algorithm for finding a maximum weightK-independent set on interval graphs ⋮ An annotated bibliography on guaranteed graph searching ⋮ An efficient algorithm for finding a maximum weight 2-independent set on interval graphs ⋮ Maximum weightk-independent set problem on permutation graphs ⋮ The summation and bottleneck minimization for single-step searching on weighted graphs

Cites Work

• The maximum k-colorable subgraph problem for chordal graphs
• Trapezoid graphs and their coloring
• On chain and antichain families of a partially ordered set
• The edge inducibility of graphs
• Unnamed Item
• Unnamed Item