For the algorithmic aspects of graph parameters, we first present a polynomial-time algorithm approximating the minimum number of vertices of an input graph whose removal leads to a ptolemaic graph within a constant factor. For a family $\mathcal{F}$ of graphs and an integer $r$, the $(r,\mathcal{F})$-covering number of a graph $G$ is the minimum size of a set $D\subseteq V(G)$ such that every induced subgraph of $G$ isomorphic to a graph in $\mathcal{F}$ is at distance at most $r$ from $D$, and the $(r,\mathcal{F})$-packing number of $G$ is the maximum size of a collection of subsets $A_1,\ldots A_\ell$ of $V(G)$ such that each of them induces a subgraph of $G$ isomorphic to a graph in $\mathcal{F}$, and for all $1\leq i

그래프 파라미터의 알고리듬적 측면에 관한 연구로, 주어진 그래프에서 최소 꼭짓점을 제거하여 ptolemaic 그래프가 되도록 하는 문제의 최소 꼭짓점 제거수를 상수배 이내로 근사하는 알고리듬을 제시한다. 그래프 집합 $\mathcal{F}$와 정수 $r$에 대하여, $\mathcal{F}$에 있는 그래프와 동형인 $G$의 모든 유도된 하위그래프와 항상 거리가 $r$ 이내인 집합의 최소 크기를 $G$의 $(r,\mathcal{F})$ 덮개수라 하며, 서로 거리가 $r$보다 크고 각각 $\mathcal{F}$에 있는 그래프와 동형인 $G$의 하위그래프를 유도하는 $V(G)$의 부분집합 모음의 최대 크기를 $G$의 $(r,\mathcal{F})$ 포장수라 한다. 우리는 $\mathcal{F}$가 연결된 그래프로만 구성된 유한 집합일 때, 주어진 그래프 $G$를 더 작은 그래프 $G'$로 변환하여 $G$의 $(r,\mathcal{F})$ 덮개수 혹은 포장수가 정수 $k$ 이하일 필요충분조건이 $G'$의 대응되는 $(r,\mathcal{F})$ 덮개수 혹은 포장수가 $k+1$ 이하가 되도록 하는 다항식 시간 알고리듬을 제시한다. 그래프 파라미터의 구조적 측면에 관한 연구로는 Bonnet, Kim, Thomass\'{e}, Watrigant에 의하여 도입된 (J. ACM, 2022) 그래프의 쌍둥이 너비에 대한 여러 한계를 제시한다. 첫 번째로, 그래프의 꼭짓점 개수와 변 개수 각각에 대한 쌍둥이 너비의 상계를 제시하고, Paley 그래프의 쌍둥이 너비를 정확히 계산함으로써 꼭짓점 개수에 대한 상계의 점근값이 더 이상 개선될 수 없음을 보였다. 두 번째로, 무작위 그래프의 쌍둥이 너비를 점근적으로 계산하고, 무작위 그래프의 작은 쌍둥이 너비에 대한 문지방 함수들을 제시하였다. 마지막으로 모든 $3$ 이하의 정수 $d$에 대하여, 다중그래프 $G$의 각 변을 $3$ 이상의 경로로 바꾸어서 얻어진 그래프가 $d$ 이하의 쌍둥이 너비를 가질 필요충분조건이 $G$가 유한 개의 그래프를 minor로 가지지 않음을 보였다.