학술
기타
A coarse block-cut tree theorem
arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.Abstract
We prove a coarse analogue of the classic fact that every graph can be decomposed along its cut-vertices into $2$-connected components.
Precisely, we prove that for every graph $G$ and a positive integer $d$, $G$ admits a tree decomposition whose adhesion sets have weak diameter at most $3d+2$ so that no two vertices $u,v$ lying in the same bag can be separated by a set of weak diameter at most $d$ whose distance from $u$ and $v$ is more than $d$.
By the Coarse Menger's Theorem for two paths, this condition admits also a dual formulation, phrased in terms of the existence of two paths that are far from each other and connect the vicinity of $u$ with the vicinity of $v$.
이 뉴스, 어떠셨어요?
한 번의 탭으로 반응을 남겨요 · 로그인 불필요
관련 뉴스
관련 뉴스 제보는 로그인 후 가능합니다.
'research' 카테고리 뉴스
arXiv의 다른 기사
Evaluating SageMath-Augmented LLM Agents for Computational and Experimental Mathematics
arXiv CS.AI
The Harness Effect: How Orchestration Design Sets the Token Economics of Enterprise Agentic AI
arXiv CS.AI
Grounding Spatial Relations in a Compact World Model: Instruction Leakage and a Goal-Free Dynamics Fix
arXiv CS.AI