NotesFAQContact Us
Search Tips
Peer reviewed Peer reviewed
Direct linkDirect link
ERIC Number: EJ1115770
Record Type: Journal
Publication Date: 2012-Oct
Pages: 22
Abstractor: As Provided
ISSN: EISSN-1932-6246
Human Performance on Hard Non-Euclidean Graph Problems: Vertex Cover
Carruthers, Sarah; Masson, Michael E. J.; Stege, Ulrike
Journal of Problem Solving, v5 n1 Article 5 p34-55 Oct 2012
Recent studies on a computationally hard visual optimization problem, the Traveling Salesperson Problem (TSP), indicate that humans are capable of finding close to optimal solutions in near-linear time. The current study is a preliminary step in investigating human performance on another hard problem, the Minimum Vertex Cover Problem, in which solvers attempt to find a smallest set of vertices that ensures that every edge in an undirected graph is incident with at least one of the selected vertices. We identify appropriate measures of performance, examine features of problem instances that impact performance, and describe strategies typically employed by participants to solve instances of the Vertex Cover problem.
Purdue University Press. Stewart Center Room 370, 504 West State Street, West Lafayette, IN 47907. Tel: 800-247-6553; Fax: 419-281-6883; e-mail: pupress@purdue,edu; Web site:
Publication Type: Journal Articles; Reports - Research
Education Level: Higher Education; Postsecondary Education
Audience: N/A
Language: English
Sponsor: N/A
Authoring Institution: N/A
Grant or Contract Numbers: N/A