LAB LOGA page on LabLog, a review site (not the lab's official page)
Graph Theory, Theoretical Computer Science, and Algorithms Lab
Machine-translated · View original
Discrete mathematics that uncovers the structure of graphs to get at the essence of combinatorial optimization.
AboutAbout the lab
From graph structure to the essence of optimization.
Prof. Kita studies discrete mathematics and theoretical computer science, centered on graph theory, combinatorial optimization, and algorithms.
Motivated by optimization theory and algorithm design, the professor investigates the structure of graphs.
The lab does not do applied research; its style is to build theory by accumulating theorems and proofs.
The lab accepts undergraduate students from the Department of Mathematics in the School of Science for graduation research, and accepts graduate students through the Graduate School of Mathematics.
Key terms
- Graph
- A structure made of points and lines (edges) connecting them. It expresses the connections in a network mathematically
- Combinatorial optimization
- A theory that deals with problems of finding the best choice among a finite number of possible choices
- Canonical decomposition
- A way of dividing a graph that is determined uniquely, making the structure of the whole graph easy to see
ResearchResearch themes
The lab studies graph theory, combinatorial optimization, and algorithms, investigating the structure of graphs motivated by optimization theory and algorithm design. In particular, it works on deriving canonical decompositions, which are decomposition theorems for graphs, and on their theoretical applications.
*Illustrative imageCanonical decompositions in matching theory
In matching theory, which deals with sets of edges that share no vertices (matchings), canonical decompositions are the foundation of the theory. The lab has derived a new canonical decomposition that applies to any graph and includes the previously known canonical decompositions, and applies it to, for example, alternative proofs of classical theorems.
*Illustrative imageCanonical decompositions for T-joins
T-joins (parity factors) are a classical object of discrete optimization that includes a variety of path problems, such as the shortest path problem and the Chinese postman problem. Their properties are far more complex than those of matchings and the foundations of the theory are underdeveloped, so the lab is working to build a theory of canonical decompositions for them.
MembersFaculty
- Associate ProfessorNanao Kita
VoicesStudent voices
Ratings and reviews reflect the experiences of individual current or former students, not the lab's official views. Whether a lab has reviews, or how many, says nothing about the lab itself.
Students who take part in an interview may receive a thank-you gift worth ¥1,000, regardless of what they say.
Student ratings (0 students)
--
--
--
--
--
--
Student voices answer questions like these
- What's great about this lab?
- What did you learn after joining?
- What's the vibe, and what is the professor like?
- Who is this lab for?
- Where do graduates go?
Your experience can help younger students choose their lab. Your name won't be shown.
Write a lab reviewAnonymous · Your draft is saved if you stopRelatedLabs similar to Graph Theory, Theoretical Computer Science, and Algorithms Lab
Combinatorics, Theoretical Computer Science, Algorithm Theory, and Optimization Theory Lab (Hiroshi Hirai)School of Science, Department of MathematicsResearch on optimization and algorithms, with interest in th…
Quantum Information Theory, Theoretical Computer Science, and Algorithms LabSchool of Science, Department of MathematicsTheoretical computer science: graph algorithms, algebraic al…
Fourier Analysis and Partial Differential Equations LabSchool of Science, Department of MathematicsTheory of nonlinear partial differential equations. Nonlinea…
Naito LabSchool of Science, Department of MathematicsStudies variational problems arising from differential geome…The information on this page is compiled by the LabLog team from the lab's public information and interviews. For corrections or removal requests, please contact LabLog, not the lab.
Report an errorAbout the images
The top and research theme images are illustrative and were not taken at the lab. They are cropped from Wikimedia Commons images. Cropped CC BY-SA images are provided under the same CC BY-SA license as the original (version shown on each line).
- Top image: “Moreno Sociogram 5th Grade” Martin Grandjean / CC BY-SA 4.0 (cropped)
- Canonical decompositions in matching theory: “Perfect matching 1” RRPPGG / CC BY-SA 4.0 (cropped)
- Canonical decompositions for T-joins: “Shortest path example graph” Shirisha Gongati / CC0 (cropped)
- Related lab (Combinatorics, Theoretical Computer Science, Algorithm Theory, and Optimization Theory Lab (Hiroshi Hirai)): “Imperialist-competitive-algorithm-flowchart-bg” Original author: Icasite Author of the derivative work: Spiritia / CC BY-SA 3.0 (cropped)
- Related lab (Quantum Information Theory, Theoretical Computer Science, and Algorithms Lab): “Google Sycamore Chip 001” Google (https://www.youtube.com/channel/UCK8sQmJBp8GCxrOtXWBpyEA) / CC BY 3.0 (cropped)
- Related lab (Fourier Analysis and Partial Differential Equations Lab): “Ocean waves water” Jon Sullivan / Public domain (cropped)
- Related lab (Naito Lab): “Carbon lattice diamond” GYassineMrabetTalk✉ This structure was created with PyMOL. / Public domain (cropped)
About LabLog
LabLog is a lab review app for students only. Student members at each university interview students in labs and publish what they say. Student voices can only be read by students who sign up with a university email address. Operated by bestiee Inc.
Learn more about LabLog ↗Search engines and AI may reference the basic lab info and rating summaries on this page and the description of LabLog. Student voices are for student members only. Automated collection by programs (scraping, or input to or training of AI) is prohibited under Article 8 of the Terms of Service. If you need data for research or analysis, please contact us.