A new proof of Delahan's induced-universality result
이 논문은 스타인하우스 삼각형의 생성 인덱스 집합 개념을 활용하여, 개의 정점을 가진 모든 단순 그래프가 개의 정점을 가진 스타인하우스 그래프의 유도 부분 그래프로 나타난다는 델라한의 정리에 대한 짧고 자기완결적인 새로운 증명을 제시합니다.
💻 Category
cs.DM
48 편의 논문
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
이 논문은 행과 열의 순서 제약 조건을 가진 격자 퍼즐의 해 존재 조건을 분석하고, 해의 개수를 훅 길이 공식으로 계산하며, 해가 없는 경우의 최소 수정 알고리즘을 제시하고 일반화된 버전의 NP-완전성을 증명합니다.
WELLDOC property for words generated by morphisms
이 논문은 무한 단어의 '균등 분포 발생 (WELLDOC)' 성질을 정의하고, 특히 문자열 사상에 의해 생성된 단어에 대해 이 성질을 판별하는 기준을 제시합니다.
A characterization of interval nest digraphs
이 논문은 모든 정점 에 대해 가 에 포함되는 구간 표현을 갖는 구간 네스트 방향 그래프를 금지된 패턴을 갖는 정점 선형 순서인 '네스트 순서'로 완전히 특징짓는 결과를 제시합니다.
A note on approximating the average degree of bounded arboricity graphs
본 논문은 bounded arboricity 그래프의 평균 차수를 근사하는 Eden, Ron, Seshadhri 의 기존 알고리즘을 파라미터 탐색으로 인한 로그 인자 손실 없이 명확하게 제시하고, 쿼리 복잡도로 -근사치를 제공하는 알고리즘을 상세히 설명합니다.
Digraph Branchings and Matrix Determinants
이 논문은 행렬의 행렬식을 방향 그래프의 가지치기 (arborescences) 가중치 합과 연결하는 새로운 행렬-트리 정리를 제시하고, 이를 통해 모든 소행렬식 정리를 증명하며 이산 상태 시스템의 시간 진화 계산과 행렬식 계산 전략에 적용합니다.
Models of random spanning trees
이 논문은 무작위 최소 신장 트리 (MST) 의 수학적 성질을 정량적으로 연구하기 위한 도구를 개발하고, 가중치가 동일한 분포에서 독립적으로 추출되는 표준 사례부터 임의의 분포에서 독립적으로 추출되는 곱측도 (product measures) 에 이르는 일반화까지 다루고 있습니다.
Linear colorings of graphs
이 논문은 선형 색수 (linear chromatic number) 의 성질을 연구하여 여러 그래프 클래스에서 기존 상한을 개선하고, 트레드깊이 (treedepth) 와의 관계에 대한 기존 추측을 더 정교하게 다룹니다.
DRESS and the WL Hierarchy: Climbing One Deletion at a Time
이 논문은 -DRESS 프레임워크가 CFI 그래프 쌍을 구별한다는 무조건적 증명과 WL-Deck 분리 가설 하에 모든 그래프에서 -WL 보다 강력하다는 조건부 증명을 통해, 기존 실증적 연구에 대한 이론적 근거를 제시합니다.
Binomial Random Matroids
이 논문은 이항 확률 모형을 통해 무작위 기저 집합이 매트로이드를 정의할 확률의 점근적 거동을 규명하고, 희소 포빙 (sparse paving) 매트로이드의 성질을 분석하며, 이를 통해 가 에 따라 느리게 증가하는 경우에도 매트로이드 수에 대한 기존 추정을 개선하는 결과를 제시합니다.
Additive Subtraction Games
이 논문은 1982 년 'Winning Ways'에 소개되었으나 완전한 증명이 부재했던 가법 뺄셈 게임의 원제 2 차(regime) 에 대한 P-위치에 대한 폐쇄형 공식을 검증하고, 각 nim-값 수열이 고전적인 P-위치의 선형 이동 위에 존재함을 증명합니다.
M-Polynomial of Product Graphs
이 논문은 직교, 직접, 강, 사전, 대칭차, 부인, 시에르핀스키 곱 등 다양한 그래프 곱에 대해 M-다항식을 계산하는 명시적이고 간결한 공식을 제시하여, 그래프 구성 하에서 정점 차수 상호작용이 어떻게 전파되는지에 대한 통합된 구조적 설명을 제공합니다.
Mean-based incomplete pairwise comparisons method with the reference values
이 논문은 기준 값을 활용하여 불완전 쌍대 비교 행렬의 가중치 벡터를 계산하는 두 가지 확장된 추정 방법 (산술 및 기하학적 HRE) 을 제안하고, 특히 기하학적 방법의 최적성과 해의 존재성을 증명하며 산술 방법의 해 존재 조건을 제시합니다.
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
이 논문은 갈라이 - 밀그람 정리를 확장하여 독립수 (independence number) 를 매개변수로 하는 고정 매개변수 tractable (FPT) 알고리즘을 제시함으로써, 주어진 그래프가 개 미만의 경로로 커버될 수 있는지 판별하는 문제를 해결하고, 이를 통해 3 이하의 독립수를 가진 그래프의 해밀턴 경로 존재 여부 판별 등 다양한 그래프 문제에 대한 새로운 알고리즘적 통찰을 제공합니다.
Block-Separated Overpartitions: Fibonacci Structure and Euler Factorization
이 논문은 인접한 서로 다른 부분 블록이 모두 오버라인되지 않는 '블록 분리 오버파티션'을 도입하여, 그 내부 구조가 피보나치 수열에 의해 지배됨을 보이고 생성함수의 오일러 곱 전개, 점화식, 그리고 점근적 성장률 등을 규명했습니다.
Induced Minors and Coarse Tree Decompositions
이 논문은 완전 이분 그래프와 격자 그래프를 유도 마이너로 배제하는 그래프가 로그 다항식 크기의 거리 16-독립수 제한을 가진 거친 트리 분해 구조를 가진다는 Chudnovsky 등의 추측을 약화시킨 형태로 증명했습니다.
Homomorphisms of (n,m)-graphs with respect to generalised switch
이 논문은 (n,m)-그래프에 대한 일반화된 스위치 연산을 제안하고 이를 통해 호모모피즘의 기본 성질을 규명하며, 2004 년과 2012 년에 제기된 열린 문제들을 해결하고 범주론적 곱과 색수 이론을 확장하는 포괄적인 연구 결과를 제시합니다.
The Complexity of Distance- Dominating Set Reconfiguration
이 논문은 거리- 지배 집합 재구성 문제에서 일 때 -완전인 분할 그래프가 일 때 에 속한다는 복잡도 이분법을 증명하고, 트리에서의 선형 시간 알고리즘을 제시하며, 평면 그래프 및 이분 그래프 등 다른 그래프 클래스에 대한 -완전성 결과를 확장합니다.
On the Polynomial Kernelizations of Finding a Shortest Path with Positive Disjunctive Constraints
이 논문은 양의 분해적 제약 조건 하의 최단 경로 문제에 대한 매개변수 복잡성 연구를 통해, 해의 크기나 H 의 구조적 속성을 매개변수로 하여 다항 커널화 및 고정 매개변수 가용성 결과를 제시합니다.
Block encoding the 3D heterogeneous Poisson equation with application to fracture flow
이 논문은 3 차원 이종 포아송 방정식의 블록 인코딩을 구축하여 지하수 흐름과 같은 실제 문제에 양자 선형 시스템 알고리즘을 적용하는 타당성을 분석하고, 전제조건의 적용 한계를 지적하면서도 3 차원 구조를 활용한 양자 알고리즘이 기존 고전적 방법보다 우수한 시간 복잡도와 메모리 효율을 제공할 수 있음을 보여줍니다.