DIMACS DCI '02

High School Student Research Conference 2003 Abstracts


Imran Amjad, Natasha Giurato, Shaun Light, Jonathan Williams
White Plains High School, White Plains, NY

Three Door Entrance Problem
Supervised by Lisa Weber, DCI 2000

In this problem our group had to decide if the 3 entrance doors chosen by the school administration allowed the students to get to class with the shortest average distance. We thought this would be a good problem to choose because if we come up with a better solution to this problem, it might be taken into consideration by the principal. We created a graph that modeled the entire building and plotted every classroom on it. We found mathematically that the 3 doors chosen by the school were not the most efficient ways to get to class for all students. We recommend there should be more doors that allow students to enter the building. There are buildings that have a long distance between the entrance doors chosen by the school, which does not allow for the shortest average distance.



Charles Andrewscavage, James Kaminski, Tracy Marriott, Ryan McCulloch
Seton Catholic High School, Pittston, PA

Comparing Algorithms for Searching Graphs Using C++
Supervised by James Kupetz, DCI 2002

Let n be the number of vertices and e be the number of edges in a graph G. G can be represented in a two-dimensional format or a one-dimensional format. We compare the efficiency of these two formats as n increases. We also formulate different algorithms for searching for triangles in G and compare the speed of these algorithms as n and e increase.



Joey Aufiero, Mark Paonessa, Lindsay Zoller
White Plains High School, White Plains, NY

Restaurant Dilemma
Supervised by Lisa Weber, DCI 2000

When a restaurant owner comes to White Plains they? re faced with the problem of where the restaurant should be located. The location and distance of the students? houses helps them determine where to place the restaurants. Our project consisted of plotting the houses of each student to help find the best location for each restaurant. The houses were plotted as vertices. To connect the houses to one another we plotted vertices at all intersections. The location of the vertices determined the distance between the restaurants and the houses. We then plotted bus stops and a bus route, again considering all intersections as vertices. We found that even if we place the restaurants close to one another they may have the same number of customers because the students live so far apart from one another. The graph would help a restaurant owner determine the distances from their restaurants to each of the houses, making it easier to decide on a location.



Victoria Braga, Danielle Brady, Marilee Sobrinski and Allison Young
Upper Township Middle School, Petersburg, NJ

The Ins and Outs of Guarding the Art
Supervised by Dolores Endicott, DCI 2002

We considered how to guard an art gallery using vertex guards. We found the shape that for any given number of sides required the most number of guards. Using this shape a table was developed to show the relationship between the number of sides in the shape and the number of guards that were always sufficient and sometimes necessary to guard the figure. The pattern shown in the table aided us in discovering a formula that would give us this number of guards. Our task was then to determine the most efficient way to place the guards. We first did this for polygonal shapes then extended this to more specific shapes like orthogonal ones. We considered vertex guards that were guarding the inside and vertex guards that were guarding the outside of our figures. By comparing theses findings we were able to make a few generalizations.



Stephen D'Auria, Michael Freeman, Nicholas Hurl, Justin Joseph, Luke Joseph, Elijah Pearce, Zac Zuschlag
Kennedy Catholic High School, Hermitage, PA

Orcs, Goblins, and Trolls, Oh My! The Domination of Middle Earth
Supervised by Janelle Stufft, DCI 2002

This presentation will focus on step domination. We define step domination as domination of a graph where each vertex is dominated by a vertex of strength k at most k edges away. In our project, k can equal 1,2,3, or 4. We have used a map of Middle Earth from J.R.R. Tolkien's The Lord of the Rings and developed 3 subgraphs from it. In order to do this we took the major cities of Middle Earth and made them vertices. Then we considered the different peoples of Middle Earth, such as elves, and calculated the strength of each group (army). We then dominated each subgraph by using step domination as defined above. In addition, we combined the subgraphs to reach our ultimate goal, domination of Middle Earth.



Amanda Denemark, Brad Fawcett, Nick Fisher, Meghana Shenoi
The Charter School of Wilmington, DE

Exploiting the Senior Class
Supervised by Chuck Biehl, DCI Lead Teacher

Inspired by recent work by James Abello of DIMACS on massive graph mining, we constructed a weighted acquaintance graph for the senior class at the Charter School of Wilmington, using edge weights to quantify the strength of friendships. We iteratively contracted the graph to try to identify superior and inferior weighted cliques. Our goal is to contract the graph to produce a weighted forest from which we hope to be able to exploit the entire graph based on identifying who the major influences are in the school.



Jeff Dinitz, Keynote Speaker
University of Vermont

Scheduling Tournaments and Leagues

The talk will survey some of the problems that come up when you have to schedule a tournament or a league. Although there are standard solutions that go by the name "combinatorial designs," the real world (e.g., your mother's golf tournament) often presents additional considerations and constraints that lead to interesting problems. In this talk we will discuss how one might construct a round robin tournament. We will then survey some known results on tournaments that satisfy additional balance conditions.



Michele Duskin, Amanda Genovino, Jhanese Alston, Emily Schlam, Leslie Isaksen, Lauren Heteji, Jennifer Heoke
(Presentation via video tape)

Livingston High School, Livingston, NJ

How well connected is the Senior Class at Livingston High School
Supervised by David Hyman, DCI 2002

By using a simple survey and graph theory and , how can you tell the level of connectedness of a population of people. What useful information can be drawn from the graphs that can benefit the school and community.



Gaelle Erisnor, Yun Feng, J.P. Lopes, Carolina Chicaiza, Xin Lei Zhao, Simon Dabre
The International High School @LGCC, LIC, NY

Radio Frequency Assignment
Supervised by Persheen Maxwell, DCI 2002

We used vertex labeling to assign frequencies to radio stations that had overlapping broadcast areas. When these areas overlap, there is interference where the overlap takes place. We used graph labeling to solve the problems of overlapping frequencies.



Jaiquan Eason
White Plains High School, White Plains, NY

Konigsberg Bridge Problem
Supervised by Christine Spatola, DCI 2002

My research project focuses on the Konigsberg Bridge Problem, in particular, Euler paths and circuits. My research focuses on various algorithms and theories that will help support my project.



Omar Garcia, Fabian Quinones, Lele Huang, Fei Xie, Darunphanth Soncharoen, Edyta Chrzanowska
The International High School @LGCC, LIC, NY

Polyhedra Coloring
Supervised by Persheen Maxwell, DCI 2002

We used vertex, edge, and region coloring to try to determine the minimum number of colors need to color the Regular Polyhedra. We then considered how this would change if we included the truncated version of the regular polyhedra. The regular polyhedra are Tetrahedron, Hexahedron, Octahedron, Dodecahedron and the Icosahedron.



Jonathan Hernandez, Eduardo Fuentes and Angel Rios
White Plains High School, White Plains, NY

Scheduling Abstract
Supervised by Christine Spatola, DCI 2002

We completed the Scheduling project that involved the FIFA 2002 World Cup and the connection to the concept of directed graphs in graph theory.



Yuechan Hu, Nagina Begun, Maria Jose Carangui, Yuriy Vanchytesky, Alex Tarasov, Qiong Li
The International High School @LGCC, LIC, NY

Optimizing Networks (Traveling Salesperson Problem)
Supervised by Persheen Maxwell, DCI 2002

Optimizing networks is to find the most efficient routes through networks. We used the idea of spanning trees and circuits to investigate networks and the traveling salesperson problem in hopes of finding the most efficient route.



Joseph Kerr, Peter Maginnis, John Tencer
Dobyns-Bennett High School, Kingsport, TN

The Olympic Ring Problem
Supervised by Tara Harrell, DCI 2002

In this presentation, we consider the Olympic Ring Problem, proposed by the University of Sydney, Australia in the year 2000. The problem involves labeling the regions of the Olympic Games' Rings with consecutive non-repeating natural numbers. These labels should be allocated in a way that any circle contains a constant sum. We pose a system for labeling odd paths. As well as showing specific graphs that have no labeling. Suggestions for further research are given.



Cody Morelock, Michael Spain
Dobyns-Bennett High School, Kingsport, TN

Finding the Search Number of a Graph
Supervised by Tara Harrell, DCI 2002

In this presentation, we consider finding the search number of a graph. We will define search number, as well as identify the search number of various graphs. Such results include paths, cycles, stars, fans, wheels, and trees. Suggestions for further research will be given.



Darren Mosley, Joanna Rotonde, Arturo Morales and John Siino
White Plains High School, White Plains, NY

Abstract for Domination : Video Camera Surveillance
Supervised by Christine Spatola, DCI 2002

In this group we chose to complete the project on Domination: Video Cameras Surveillance of White Plains High School. We had to determine every spot a camera should be placed in the building so that there are no gaps in the surveillance of the building. This research was done so that if the White Plains High School were to need cameras placed in the building, we would already know or have a general idea of where the cameras should be placed and how many should be set up.


Updated May 8, 2003