경로폭

Pathwidth

그래프 이론에서 그래프 G의 경로 분해는 비공식적으로 G를 "두께진" 경로 그래프로 나타내며,[1] G의 경로 폭은 G를 형성하기 위해 경로가 얼마나 두꺼워졌는지 측정하는 숫자다.보다 공식적으로 경로 디포메이션은 각 에지의 끝점이 하위 집합 중 하나에 나타나고 각 꼭지점이 하위 집합의 연속적인 하위 집합에 나타나며,[2] 경로 폭은 그러한 분해에서 가장 큰 집합의 크기보다 1보다 작다.경로폭은 간격 두께(G의 간격 수퍼그래프에서 최대 클라이크 크기보다 한 개 작음), 꼭지점 분리 번호 또는 노드 검색 번호로도 알려져 있다.[3]

경로 폭과 경로 디포메이션은 나무 폭과 나무 분해와 매우 유사하다.그들은 그래프 미성년자 이론에서 핵심적인 역할을 한다: 그래프 미성년자 아래에서 닫히고 모든 숲을 포함하지 않는 그래프의 집단은 경계가 있는 경로폭으로 특징지어질 수 있으며,[2] 경계가 닫힌 그래프 집단의 일반 구조 이론에 나타나는 "변수"는 경계가 있는 경로폭으로 특징지어진다.[4]경로폭과 경계경로폭의 그래프도 VLSI 설계, 그래프 그리기, 계산언어학 등에 응용된다.

임의 그래프의 경로 너비를 찾거나, 심지어 정확한 대략을 찾는 것은 NP-hard이다.[5][6]그러나 문제는 고정 매개변수 추적 가능하다. 그래프의 경로 너비 k가 있는지 테스트하는 것은 그래프의 크기에 따라 선형적으로 달라지지만 k에 대해서는 기본적으로 가능하다.[7]또한 나무와 같은 몇 가지 특수 등급의 그래프의 경우, 경로폭은 k에 의존하지 않고 다항 시간 내에 계산될 수 있다.[8][9]그래프 알고리즘의 많은 문제들은 경계가 있는 경로 너비의 그래프에서 그래프의 경로 디프로그래밍을 통해 효율적으로 해결될 수 있다.[10]경로 분해는 또한 경계 트리 너비의 그래프에서 동적 프로그래밍 알고리즘의 공간 복잡성을 측정하는 데 사용될 수 있다.[11]

정의

경로 너비 2와 경로 디포메이션 2가 있는 그래프 G.영상의 하단 부분은 강조하기 위해 색상이 추가된 동일한 그래프와 경로 디포메이션이다.(이 예는 Bodlaender(1994a)에 제시된 그래프를 개작한 것이며, 강조가 추가되었다.)

닐 로버트슨과 폴 세이모어(1983)는 그래프 G의 경로 배열을 그래프 미성년자에 대한 유명한 시리즈 중 첫 번째 논문에서 G의 정점 X의i 하위 집합 시퀀스로 정의하며 다음 두 가지 속성을 가지고 있다.

  1. G의 각 가장자리에 대해, 가장자리의 양쪽 끝점이 부분 집합 X에i 속하도록 i가 존재한다.
  2. 세i 지수마다 i ≤ j ≤ k, X ∩ Xkj.

이 두 속성 중 두 번째는 특정 정점을 포함하는 부분 집합이 전체 시퀀스의 연속적인 연속성을 형성하도록 요구하는 것과 동등하다.로버슨과 세이모어의 그래프 마이너 시리즈에 수록된 후기 논문의 언어로, 경로 디포메이션은 트리 분해(X,T)로, 분해의 기본 트리 T가 경로 그래프인 것이다.

경로 디포메이션의 폭은 나무i 디포메이션과 동일한i 방식으로 정의되며, G의 경로 폭은 G의 어떤 경로 디포메이션의 최소 폭이다.이 정의에서 X의i 크기에서 하나를 뺄셈은 대부분의 경로 너비 적용에서 거의 차이가 없지만 경로 그래프의 경로 너비가 1과 같도록 하는 데 사용된다.

대체 특성화

Bodlaender(1998)가 기술한 바와 같이, 경로폭은 여러 가지 동등한 방법으로 특징지을 수 있다.

접착 시퀀스

경로 분해는 이러한 모든 글루잉을 수행한 결과가 G가 되도록 시퀀스의 연속 그래프에서 정점 쌍을 식별하여 접착된 그래프i G의 시퀀스로 설명할 수 있다.그래프 G는i 경로 분해의 첫 번째 정의에서 세트 X의i 유도 서브그래프로 간주될 수 있으며, 연속 유도 서브그래프의 두 정점이 G의 동일한 정점에 의해 유도될 때 함께 접착되며, 다른 방향에서는 세트 X를i 그래프 G의i 정점 세트로 복구할 수 있다.그러면 경로 분해의 너비는 그래프i G 중 하나의 최대 정점 수보다 한 개 작다.[2]

간격두께

경로 너비가 2인 구간 그래프. ABC, ACD, CDE 및 4개의 최대 분류의 카디널리티보다 1개 작음.

그래프 G의 경로 너비는 G를 하위 그래프로 포함하는 구간 그래프의 최소 클릭 수보다 1보다 작다.[12]즉, G의 모든 경로 분해에 대해 G의 구간 슈퍼그래프를 찾을 수 있고, G의 구간 슈퍼그래프마다 G의 경로 분해도를 찾을 수 있어 분해의 폭이 구간 그래프의 클릭 수보다 한 개 작다.

한 방향으로 G의 경로 분해가 주어진다고 가정합시다.그런 다음 하나는 분해의 노드를 선상의 점(경로 순서에 따라)으로 나타내고 각 꼭지점 v를 이러한 점을 끝점으로 하는 닫힌 구간으로 나타낼 수 있다.이러한 방식으로 v를 포함하는 경로 분해 노드는 v 간격의 대표적인 지점에 해당한다.G의 정점으로부터 형성된 구간의 교차 그래프는 G를 서브그래프로 포함하는 구간 그래프다.그것의 최대 클릭은 대표 포인트를 포함하는 일련의 간격에 의해 주어지며, 그것의 최대 클릭 크기는 G의 경로 너비에 1을 더한다.

다른 방향에서 G가 clique number p + 1의 구간 그래프의 하위 그래프인 경우 G는 구간 그래프의 최대 구간에서 노드가 주어지는 width p의 경로 분해를 가진다.예를 들어, 그림에서 구간표현과 함께 표시된 구간 그래프는 5개의 노드로 이루어진 경로분해를 가지고 있는데, 이는 ABC, ACD, CDE, CDF 및 FG의 5개의 최대 분류에 해당한다. 최대 클릭 크기는 3이고 이 경로분해의 폭은 2이다.

경로 폭과 구간 두께 사이의 등가성은 나무 폭과 주어진 그래프가 하위 그래프인 화음 그래프의 최소 클라이크 수(최소 1) 사이의 등가성과 매우 유사하다.구간 그래프는 코드 그래프의 특별한 경우로, 코드 그래프는 구간 그래프가 경로의 하위 경로의 교차 그래프인 방식을 일반화하는 공통 트리의 하위 트리의 교차 그래프로 나타낼 수 있다.

정점분리수

그래프 G의 정점이 선형적으로 정렬되어 있다고 가정합시다.그런 다음, G의 정점 분리 번호는 각 정점 v에 대해 대부분의 정점이 순서에서 v보다 빠르지만 이웃으로 v 또는 이후 정점이 있는 최소 숫자 s이다.G의 정점 분리 번호는 G의 선형 순서의 최소 정점 분리 번호다.정점 분리 번호는 엘리스, 수드버러 & 터너(1983)에 의해 정의되었으며, G의 경로폭과 같다.[13]이것은 구간 그래프 편파 숫자와 이전의 동등함에서 따온 것이다: G가 모든 구간 끝점이 구별되는 방식으로 표시된 구간 그래프 I의 하위 그래프인 경우, I 간격의 왼쪽 끝점의 순서는 정점 분리 번호를 I의 편파 번호보다 1 더 적게 가진다.그리고 다른 방향에서 G의 선형 순서로부터 정점 v에 대한 구간의 왼쪽 끝점이 순서상 위치이고 오른쪽 끝점이 순서상 마지막인 v의 인접 위치인 구간표현을 유도할 수 있다.

노드 검색 번호

그래프의 노드 검색 게임은 일련의 검색자들이 그래프에 숨어 있는 도망자를 추적하기 위해 협력하는 추적-에피션의 한 형태다.검색자는 그래프의 정점에 배치되고, 도망자는 그래프 가장자리에 있을 수 있으며, 도망자의 위치와 이동은 검색자로부터 숨겨진다.각 턴에서, 검색자의 일부 또는 전부가 한 꼭지점에서 다른 꼭지점으로 이동할 수 있으며(임의적으로, 반드시 가장자리를 따라 이동할 필요는 없음) 그 다음, 도망자는 검색자가 점유한 꼭지점을 통과하지 않는 그래프 상의 어떤 경로를 따라 이동할 수 있다.도망자는 그의 가장자리의 양쪽 끝이 수색자들에 의해 점령되었을 때 잡힌다.그래프의 노드 검색 번호는 도망자가 어떻게 움직이던 간에 붙잡힐 수 있도록 보장하는 데 필요한 최소한의 검색자 수입니다.키루시스와 파파디미트리오(1985)가 보여주듯이, 그래프의 노드 검색 번호는 간격 두께와 같다.검색자의 최적 전략은 연속적인 턴으로 최소 정점 분리 번호로 선형 정렬의 분리 집합을 형성하도록 검색자를 이동하는 것이다.

경계

애벌레 나무, 경로 폭이 1인 최대 그래프.

경로 너비 k가 있는 모든 n-vertex 그래프에는 최대 k(n - k + (k - 1)/2) 에지가 있으며, 최대 경로 너비-k 그래프(경로 너비를 늘리지 않고 더 이상 에지를 추가할 수 없는 그래프)에는 정확히 이 많은 에지가 있다.최대 경로 너비-k 그래프는 k-path 또는 k-caterfilar, 두 종류의 특별한 k-tree여야 한다.k-트리(k-tree)는 정확히 n - k maximal click을 포함하는 화음 그래프로서, 각각 k + 1 정점을 포함하고 있다. 그 자체가 (k + 1)-clik가 아닌 k-tree에서, 각 최대 클릭은 그래프를 둘 이상의 성분으로 나누거나, 단일 잎 꼭지점, 즉 하나의 최대 클릭에만 속하는 정점을 포함하고 있다.k-path는 잎이 최대 두 개까지 있는 k-tree이고, k-caterfilar는 k-path의 분리형 k-clike에 각각 인접한 k-leaves로 분할할 수 있는 k-tree이다.특히 경로폭 1의 최대 그래프는 정확히 애벌레 나무다.[14]

경로 디포메이션은 나무 디포메이션의 특별한 경우이기 때문에, 어떤 그래프의 경로 폭은 나무 너비보다 크거나 같다.또한 경로 폭은 그래프 정점의 최적 선형 배열에서 낮은 번호와 높은 번호 정점 사이의 절단을 가로지르는 최소 에지 수인 컷 너비보다 작거나 같다. 이는 정점 분리 번호, 높은 번호의 이웃이 있는 낮은 번호 정점의 수가 mos에서 가능하기 때문이다.t 절단된 가장자리 수와 동일하다.[15]비슷한 이유로, 절단 너비는 최대 경로 너비에 주어진 그래프에서 정점의 최대 정도를 곱한 값이다.[16]

n-vertex 숲에는 경로폭 O(log n)가 있다.[17]숲에서는 항상 일정한 수의 정점을 찾을 수 있으며, 그 정점을 제거하면 각각 최대 2n/3 정점을 가진 두 개의 작은 하위 숲으로 분할될 수 있다.이들 두 하위 포리스트 각각을 재귀적으로 분할하여 그들 사이에 분리 정점을 배치함으로써 형성된 선형 배열에는 로그 정점 검색 번호가 있다.그래프의 트리-디포메이션에 적용된 동일한 기법은 n-베르텍스 그래프 G의 트리 너비가 t이면 G의 경로 너비가 O(t log n)임을 보여준다.[18]외부 평면 그래프, 직렬-병렬 그래프, 할린 그래프는 모두 경계 트리 너비를 가지기 때문에 최대 로그 경로 너비를 가지기도 한다.

그래프 G의 선 그래프 L(G)은 G의 각 가장자리에 정점이 있고 L(G)의 두 정점이 끝점을 공유할 때 인접해 있다.선 그래프가 선형 클라이크 너비를 경계한 경우에만 그래프의 모든 계열은 경계 경로 너비를 경계로 설정했다. 여기서 선형 클라이크 너비는 클라이크 너비에서 분리 연합 작업을 하나의 새로운 꼭지점에 인접한 작업으로 대체한다.[19]정점이 3개 이상인 연결된 그래프가 최대 도 3을 갖는 경우, 그 절단 너비는 선 그래프의 정점 분리 번호와 동일하다.[20]

모든 평면 그래프에서 경로 폭은 정점 수의 제곱근에 최대 비례한다.[21]이 너비로 경로 디포케이션을 찾는 한 가지 방법은 (위에서 설명한 숲의 로그 너비 경로 디포메이션과 유사하게) 평면 분리기 정리를 사용하여 O(√n) 정점의 집합을 찾고, 이 정점을 제거하여 그래프를 각각 최대 2n/3 정점의 두 하위 그래프로 분리하고, 반복적으로 구성된 경로 디컴파운드를 통합하는 것이다.이 두 개의 서브그래프 각각에 대한 오션동일한 기법이 유사한 분리막 정리가 있는 어떤 종류의 그래프에도 적용된다.[22]평면 그래프와 마찬가지로 고정 보조 닫힘 그래프 패밀리의 그래프에는 크기 O(√n)의 구분자가 있으므로 고정 보조 닫힘 패밀리의 그래프의 경로 너비는 다시 O((n)가 된다.[23]일부 평면 그래프 클래스의 경우 그래프의 경로 폭과 그 이중 그래프의 경로 폭은 서로 상수 요인 내에 있어야 한다. 이 형식의 한계는 연결된 외부 평면 그래프와[24] 다면 그래프로 알려져 있다.[25]2개의 연결된 평면 그래프의 경우 이중 그래프의 경로 너비가 선 그래프의 경로 너비보다 작다.[26]평면 그래프의 경로 폭과 평면 그래프의 이중 폭이 나머지 경우 항상 서로 일정한 요인 내에 있는지 여부는 열려 있다.

그래프의 일부 등급에서, 경로 폭과 나무 폭은 항상 서로 동일하다는 것이 입증되었다: 이는 cographs,[27] permution graphs,[28] 비교가능성 그래프의 보완 [29]및 구간 순서의 비교가능성 그래프의 경우 사실이다.[30]

수학의 미해결 문제:

-vertex 세제곱 그래프의 가능한 최대 경로 너비는?

(수학에서 더 풀리지 않은 문제)

입방형 그래프에서, 또는 일반적으로 최대 정점 3을 갖는 그래프에서, 경로 폭은 최대 n/6 + o(n)이며, 여기서 n은 그래프에서 정점 수입니다.경로폭 0.082n의 입방형 그래프가 존재하지만, 이 하한과 n/6 상한 사이의 간격을 어떻게 줄일지는 알 수 없다.[31]

컴퓨팅 경로 삭제

k가 입력의 일부로 주어진 변수인 경우, 주어진 그래프의 경로폭이 최대 k인지 여부를 결정하는 것은 NP-완전이다.[5]임의의 n-vertex 그래프의 경로 너비를 계산하기 위해 가장 잘 알려진 최악의 경우 시간 범위는 일부 상수 c의 경우 O(2n n) 형식이다c.[32]그럼에도 불구하고, 몇몇 알고리즘은 경로 폭이 작을 때, 입력 그래프의 클래스가 제한되었을 때, 또는 대략적으로 경로 디플렉션을 더 효율적으로 계산하는 것으로 알려져 있다.

고정-모수 추적성

경로폭은 고정 매개변수 추적 가능: 어떤 상수 k에 대해 경로폭이 최대 k인지 여부를 테스트할 수 있으며, 그렇다면 선형 시간 내에 폭 k의 경로 디포케이션을 찾을 수 있다.[7]일반적으로 이러한 알고리즘은 두 단계로 작동한다.첫 번째 단계에서 그래프에 경로폭 k가 있다는 가정은 최적은 아니지만, 폭이 k의 함수로 경계될 수 있는 경로배열 또는 트리배열을 찾는 데 사용된다.두 번째 단계에서는 최적의 분해를 찾기 위해 동적 프로그래밍 알고리즘이 이 분해에 적용된다.그러나 이러한 유형의 알려진 알고리즘에 대한 시간 범위는 k의2 기하급수적인 것으로, 가장 작은 k 값을 제외하고 실용적이지 않다.[33]사례 k = 2의 경우, 경로폭-2 그래프의 구조적 분해에 기초한 명시적 선형 시간 알고리즘은 de Fluiter(1997)에 의해 제공된다.

그래프의 특수 클래스

Bodlaender(1994)는 다양한 특수 등급의 그래프의 경로 너비를 계산하는 복잡성을 조사한다.G가 경계도 그래프,[34] 평면 그래프,[34] 경계도,[34] 화음도,[35] 화음도,[36] 비교가능성 그래프의 보완,[29] 쌍방향 거리-계속 그래프로 제한될 때 그래프 G의 경로 폭이 최대 k인지 여부를 결정하는 것은 NP-완전성을 유지한다.[37]또한 초당파 그래프, 화음계측 그래프, 거리계측 그래프, 원그래프 등 초당파적 거리계측 그래프를 포함하는 그래프 계열의 경우 NP-완전하다는 것이 바로 뒤따른다.[37]

그러나, 경로 너비는 나무와 숲의 선형 시간으로 계산될 수 있다.[9]그것은 또한 다항 시간에 경계 treewidth의series–parallel 그래프,outerplanar 그래프, 그리고 Halin graphs,[7]뿐만 아니라 분할 graphs,[38]활줄 graphs,[39]의 칭찬을 하도록 유도하다 반달형 graphs,[40]에 간격의 호환성 그래프 orders,에 cographs,[27]을 순열 graphs,[28]을 포함한 그래프의 경우 계산될 수 있다.30을 생성하고 inte 물론.rval 그래프 자체는 경로 폭이 그래프의 간격 표현에서 어떤 점을 포함하는 최대 간격 수보다 한 개 작기 때문이다.

근사 알고리즘

그래프의 경로 너비를 가법 상수 이내로 추정하는 것은 NP-강력하다.[6]경로폭에 대한 다항식 시간 근사 알고리즘의 가장 잘 알려진 근사비는 O(log n)3/2[41]이다.경로 너비에 대한 초기 근사 알고리즘은 Bodlaender 등(1992)과 Guha(2000)를 참조한다.제한된 등급의 그래프에 대한 근사는 Kloks & Bodlaender(1992)를 참조한다.

그래프 마이너

그래프 G의 부차는 가장자리를 수축하고 가장자리를 제거하고 정점을 제거함으로써 G에서 형성된 또 다른 그래프다.그래프 미성년자들은 몇몇 중요한 결과들이 경로폭과 관련이 있다는 깊은 이론을 가지고 있다.

숲 제외

미성년자를 대상으로 한 그래프 F 계열이 폐쇄된 경우(F 멤버의 모든 부전부는 F에 있음) 로버슨-세이모어 정리 F는 X에서 마이너스가 없는 그래프로 특징지어질 수 있는데, 여기서 X는 금지된 미성년자의 유한 집합이다.[42]예를 들어 바그너의 정리를 보면 평면 그래프는 전체 그래프 K도5, 전체 양분 그래프 K도3,3 미성년자임을 알 수 없다.F의 특성과 X의 특성은 밀접한 관계가 있는 경우가 많으며, 이러한 유형의 첫 번째 결과는 로버트슨&세이모어(1983)에 의한 것이며,[2] 경계된 경로폭과 금지된 미성년자 가족의 숲의 존재와 관련이 있다.특히 F의 모든 그래프가 최대 p의 경로 폭을 가질 수 있도록 일정한 p가 존재하는 경우 그래프의 F 패밀리를 정의하십시오.그런 다음, F에 대해 금지된 미성년자 집합 X에 적어도 하나의 숲이 포함되는 경우에만 미성년자 가족 F가 경로 너비를 경계했다.

한 방향에서, 이 결과는 증명하기 쉽다: X가 적어도 하나의 숲을 포함하지 않는다면, X-minor-free 그래프에는 경계 경로 너비가 없다.이 경우 X-minor-free 그래프에는 모든 숲이 포함되며, 특히 완벽한 이진수가 포함된다.그러나 2k + 1 수준의 완벽한 이진수 트리는 경로폭 k를 가지므로 이 경우 X-minor-free-graphs는 무한의 경로폭을 가진다.다른 방향에서 X에 n-vertex 포리스트가 있으면 X-minor-free 그래프는 최대 n - 2의 경로 너비를 가진다.[43]

경계 경로 너비에 대한 장애물

경로 너비 1 그래프에 대해 금지된 미성년자.

최대 p의 경로 너비를 갖는 특성은 그 자체로 미성년자 아래 닫힌다: G가 최대 p의 폭을 가진 경로 디포메이션이 있다면, G에서 어떤 가장자리를 제거해도 동일한 경로 디포메이션은 유효하며, 어떤 꼭지점이라도 폭을 늘리지 않고 G와 그 경로 디포메이션에서 제거할 수 있다.또한 가장자리의 수축은 수축된 가장자리의 두 끝점을 나타내는 하위 경로를 병합하여 분해 폭을 늘리지 않고도 달성할 수 있다.따라서 최대 p의 경로 너비 그래프는 제외된 미성년자의 집합 X로p 특징지어질 수 있다.[42][44]

X가p 반드시 적어도 하나의 포리스트를 포함해야 하지만, X의p 모든 그래프가 포리스트라는 것은 사실이 아니다. 예를1 들어, X는 두 개의 그래프, 즉 일곱 개의 버텍스 나무와 삼각형3 K로 구성되어 있다.그러나 X의p 나무 세트는 정확하게 특징지어질 수 있는데, 바로 이 나무들이 세 개의 작은 나무 각각에서 임의로 선택한 꼭지점에 새로운 뿌리 정점을 가장자리로 연결함으로써p − 1 X의 세 나무에서 형성될 수 있는 나무들이다.예를 들어, X의1 7번 버텍스 트리는0 X의 2번 버텍스 트리(단일 에지)에서 이와 같이 형성된다.이p 구성을 바탕으로 X의 금지 미성년자 수는 최소한 (p!)2[44]인 것으로 보일 수 있다.경로 너비-2 그래프에 대한 금지된 미성년자의 전체 집합2 X가 계산되었다. 여기에는 110개의 다른 그래프가 포함되어 있다.[45]

구조 이론

마이너 클로즈드 그래프 패밀리의 그래프 구조 정리는 그러한 패밀리의 경우 F의 그래프를 클릭섬의 각 성분에 대한 한정된 정점과 변수와 함께 경계된 속성의 표면에 삽입될 수 있는 그래프의 클릭섬으로 분해할 수 있다고 명시한다.꼭지점은 그 구성요소의 다른 꼭지점에 인접할 수 있는 정점인 반면, 소용돌이는 구성요소를 내장한 경계 유전자의 면 중 하나에 접착된 경계 경로 폭의 그래프다.소용돌이가 내장된 얼굴 주위의 정점들의 주기적 순서는 선형 순서를 형성하기 위한 사이클을 깨는 것이 경계 정점 분리 번호를 가진 순서로 이어져야 한다는 점에서 소용돌이의 경로 분해와 호환되어야 한다.[4]경로 너비가 임의의 마이너-폐쇄 그래프 패밀리에 밀접하게 연결되는 이 이론은 중요한 알고리즘 응용 프로그램을 가지고 있다.[46]

적용들

VLSI

VLSI 설계에서 정점 분리 문제는 원래 회로를 더 작은 서브시스템으로 분할하는 방법으로 연구되었는데 서브시스템 사이의 경계에 적은 수의 구성요소가 있다.[34]

Ohtsuki 외 연구진(1979)은 간격 두께를 사용하여 VLSI 회로의 1차원 레이아웃에 필요한 트랙 수를 모델링하는데, 이는 그물 시스템으로 상호 연결되어야 하는 모듈 세트에 의해 형성된다.그들의 모델에서, 정점들이 그물을 나타내는 그래프를 형성하고, 그들의 그물이 모두 동일한 모듈에 연결되면 두 정점이 에지에 의해 연결되는 그래프를 형성한다. 즉, 모듈과 그물이 하이퍼그래프의 노드와 변종들을 형성하는 것으로 해석된다면 그것들로부터 형성된 그래프는 선 그래프다.이 선 그래프의 수퍼그래프의 간격 표현은 슈퍼그래프의 색상과 함께 모듈을 선로 순서대로 트랙을 따라 배치하고 적절한 네트에 연결할 수 있도록 수평 트랙 시스템(색상당 하나의 트랙)을 따라 네트의 배열을 설명한다.구간 그래프가 완벽한 그래프라는[47] 사실은 이 유형의 최적 배열에서 필요한 색의 수가 순 그래프의 구간 완료의 클릭 수와 동일하다는 것을 의미한다.

게이트 매트릭스 레이아웃은[48] 부울 논리 회로용 CMOS VLSI 레이아웃의 특정 스타일이다.게이트 매트릭스 레이아웃에서 신호는 "라인"(수직선 세그먼트)을 따라 전파되는 반면 회로의 각 게이트는 수평선 세그먼트를 따라 놓여 있는 일련의 장치 특징에 의해 형성된다.따라서 각 게이트의 수평선 세그먼트는 게이트의 입력 또는 출력을 형성하는 각 라인의 수직 세그먼트를 교차해야 한다.Ohtsuki 등(1979년)의 레이아웃에서와 같이, 선을 정점으로 하는 그래프의 경로 폭과 대문을 가장자리로 공유하는 선 쌍을 가진 그래프의 경로 폭을 계산하면 선들이 배열될 수직 선로의 수를 최소화하는 이러한 유형의 레이아웃을 찾을 수 있다.[49]프로그래밍 가능한 논리 배열에서 접기 문제를 모형화하는 데도 동일한 알고리즘 접근법을 사용할 수 있다.[50]

그래프 그리기

경로 너비에는 도면을 그래프로 표시하는 몇 가지 응용 프로그램이 있음:

  • 지정된 교차 번호가 있는 최소 그래프에는 교차 번호 함수에 의해 경계되는 경로 너비가 있다.[51]
  • 가장자리 교차 없이 트리의 정점을 그릴 수 있는 평행선의 수는 (선들의 순서와 관련하여 인접 정점을 배치할 수 있는 방법에 대한 다양한 자연적 제한 하에서) 트리의 경로 폭에 비례한다.[52]
  • 그래프 G의 k-크로싱 h-레이어 도면은 G의 정점을 구별되는 수평선에 배치한 것으로, 이들 선 사이에 단조로운 다각형 경로로 라우팅된 가장자리는 최대 k개의 교차점이 있는 방식이다.그러한 도면이 있는 그래프는 h와 k의 함수에 의해 경계되는 경로 폭을 가지고 있다.따라서 h와 k가 모두 일정할 때, 그래프가 k-크로싱 h-레이어 도면을 가지고 있는지 여부를 선형적으로 판단할 수 있다.[53]
  • 정점과 경로폭 p를 가진 그래프는 두 개의 에지(그리드 지점들 사이의 직선 세그먼트로 표현됨)가 서로 교차하지 않도록 크기 p × p × n의 3차원 그리드에 삽입될 수 있다.따라서 경계 경로 너비의 그래프에는 선형 볼륨이 포함된 이 유형이 포함되어 있다.[54]

컴파일러 설계

고수준 프로그래밍 언어의 편찬에서 경로폭은 코드에 계산된 모든 값을 메인 메모리에 흘릴 필요 없이 기계 레지스터에 넣을 수 있도록 직선 코드(즉, 제어 흐름 분기나 루프가 없는 코드)의 시퀀스를 재정렬하는 문제에서 발생한다.이 애플리케이션에서 하나는 노드가 코드에 대한 입력 값과 코드 내의 연산에 의해 계산된 값을 나타내는 지시된 AC순환 그래프로 컴파일될 코드를 나타낸다.이 DAG에서 노드 x에서 노드 y까지의 에지는 값 x가 작업 y에 대한 입력 중 하나라는 사실을 나타낸다.이 DAG 정점의 위상학적 순서는 코드의 유효한 재정렬을 나타내며, 주어진 순서에서 코드를 평가하는 데 필요한 레지스터의 수는 순서의 정점 분리 번호에 의해 주어진다.[55]

기계 레지스터의 고정 수 w의 경우, 직선 코드 조각이 최대 w 레지스터로 평가될 수 있는 방식으로 재주문될 수 있는지 여부를 선형 시간 내에 결정할 수 있다.왜냐하면 위상학적 순서의 정점 분리 번호가 최대 w일 경우, 모든 순서의 최소 정점 분리는 더 클 수 없으므로 위에서 설명한 DAG의 방향을 무시하여 형성된 비방향 그래프는 최대 w의 경로 너비를 가져야 한다.경로 너비에 대해 알려진 고정 매개변수 축소 가능한 알고리즘을 사용하여 이 경우인지 여부를 테스트할 수 있으며, w가 상수라는 가정 하에 비간접 그래프의 경로 디프로세스를 찾기 위해 선형 시간 내에 테스트할 수 있다.경로 분해가 발견되면 동적 프로그래밍을 사용하여 w 너비(있는 경우)의 위상학적 순서를 선형 시간 내에 다시 찾을 수 있다.[55]

언어학

Kornai & Tuza(1992)는 자연 언어 처리에서 경로 폭의 적용을 설명한다.이 응용 프로그램에서 문장은 그래프로 모델링되는데, 여기서 정점들은 단어를 나타내고 가장자리는 단어 사이의 관계를 나타낸다. 예를 들어 형용사가 문장에서 명사를 수정한다면 그래프는 그 두 단어 사이에 가장자리를 가질 것이다.인간의 단기 기억력의 제한된 용량 때문에,[56] 코르나이와 투자는 이 그래프가 경계가 있는 경로 폭(더 구체적으로는 최대 6개의 경로 폭)을 가지고 있어야 한다고 주장한다. 그렇지 않으면 인간은 말을 정확하게 구문 분석할 수 없을 것이기 때문이다.

지수 알고리즘

그래프 알고리즘의 많은 문제들은 그래프의 경로 디프로그래밍에서 동적 프로그래밍을 사용함으로써 낮은 경로폭의 그래프에서 효율적으로 해결될 수 있다.[10]예를 들어, n-vertex 그래프 G의 정점에 대한 선형 순서가 정점 분리 번호 w와 함께 주어진다면, 시간 O(2 nw)에서 G의 최대 독립 집합을 찾을 수 있다.[31]경계 경로 너비의 그래프에서, 이 접근방식은 경로 너비에 의해 파라메트릭화된 고정 매개변수 추적 가능한 알고리즘으로 이어진다.[49]이러한 결과는 트리 너비에 의해 매개되는 유사한 알고리즘에 의해 요약되기 때문에 문헌에서 자주 발견되지는 않지만, 이러한 알고리즘의 공간 복잡성을 측정하는 데 있어 트리 너비 기반 동적 프로그래밍 알고리즘에서도 경로 너비가 발생한다.[11]

또한 동일한 동적 프로그래밍 방법을 제한되지 않은 경로 너비를 가진 그래프에도 적용할 수 있어 지수 시간 내에 파라미터가 없는 그래프 문제를 해결하는 알고리즘을 만들 수 있다.예를 들어, 이 동적 프로그래밍 접근방식과 입방형 그래프의 경로폭 n/6 + o(n)를 결합하면 입방형 그래프에서 최대 독립 집합은 이전에 알려진 방법보다 빠른 시간 O(2n/6 + o(n))으로 구성할 수 있음을 알 수 있다.[31]유사한 접근방식은 입방 그래프의 최대 컷 및 최소 지배적 세트 문제 및 [31]몇 가지 다른 NP-하드 최적화 문제에 대한 지수 시간 알고리즘 개선으로 이어진다.[57]

참고 항목

  • Boxicity, 구간 그래프 측면에서 임의 그래프의 복잡성을 측정하는 다른 방법
  • 자르기폭, 그래프 정점의 선형 순서의 최소 가능한 폭
  • 트리 깊이 - 패밀리가 경로를 제외하는 경우에만 마이너 닫힘 그래프 패밀리에 대해 경계되는 숫자
  • Degeneracy, 경로 폭과 최대 동일한 그래프의 sparsity에 대한 척도
  • 그래프 대역폭, 선형 그래프 레이아웃과 관련된 다른 NP-완전한 최적화 문제
  • 스트라흘러 수(Strahler number), 뿌리 없는 나무의 경로폭과 유사하게 정의된 뿌리 나무의 복잡성을 측정하는 척도

메모들

  1. ^ 디에스텔 & 쿤(2005년).
  2. ^ a b c d 로버트슨 & 시모어(1983년).
  3. ^ 보들렌더(1998년).
  4. ^ a b 로버트슨 & 시모어(2003년).
  5. ^ a b 가시와바라 & 후지사와(1979);오쓰키 외 연구진(1979년), 렝가워(1981년), 아르노보르, 코르네일 & 프로스쿠로우스키(1987년).
  6. ^ a b Bodlaender 외 연구진(1992)
  7. ^ a b c Bodlaender (1996년); Bodlaender & Kloks (1996년)
  8. ^ 보들렌더(1994년).
  9. ^ a b 뫼링(1990), 셰플러(1990), 엘리스, 수드버러 & 터너(1994), 펑 외(1998);스코디니스(2000);스코디니스(2003);쿠더트, 후크 & 마자우리치(2012년).
  10. ^ a b Arnborg(1985년).
  11. ^ a b 아스팔, 프로스쿠로스키 & 텔레(2000년)
  12. ^ 보들렌더(1998), 정리 29, 페이지 13.
  13. ^ 키너슬리(1992년), 보들라엔더(1998년), 정리 51.
  14. ^ 프로스쿠로스키&텔레(1999년).
  15. ^ Korach & Solel(1993), Leemma 3 p.99; Bodlaender(1998), Organization 47, 페이지 24.
  16. ^ Korach & Solel(1993), Leemma 1, 페이지 99, Bodlaender(1998), Organization 49, 페이지 24.
  17. ^ 코라크 & 솔렐(1993), 정리 5, 페이지 99, 보드렌더(1998), 정리 66, 페이지 30.셰플러(1992)는 n-베르텍스 숲의 경로폭에 대해 보다 엄격한 상한(2n + 1)의 통나무를3 제공한다.
  18. ^ 코라크 & 솔렐(1993), 정리 6, 페이지 100; 보드렌더(1998), 코롤라리 24, 페이지 10.
  19. ^ 구르스키&완케(2007)
  20. ^ 골로바흐(1993년).
  21. ^ 보들렌더(1998), 코롤라리 23, 페이지 10.
  22. ^ 보들렌더(1998), 정리 20, 페이지 9.
  23. ^ 알론, 시모어 & 토마스(1990).
  24. ^ 보드렌더 & 포민(2002);쿠더트, 휴크 & 세레니(2007년).
  25. ^ 포민 & 틸리코스(2007);아미니, 후크 & 페렌스(2009년).
  26. ^ 포민(2003년).
  27. ^ a b Bodlaender & Möring (1990).
  28. ^ a b Bodlaender, Kloks & Kratsch(1993).
  29. ^ a b Habib & Möring (1994년).
  30. ^ a b 가르베(1995년).
  31. ^ a b c d 포민&호위(2006년).
  32. ^ 포민 외 (2008).
  33. ^ 다우니 & 펠로우즈(1999), 페이지 12.
  34. ^ a b c d 모니엔 & 수드버러(1988)
  35. ^ 구스테트(1993년).
  36. ^ 클록스, 크래치 & 뮐러(1995년).화음 도미노는 모든 정점이 최대 두 개의 최대 정점에 속하는 화음 그래프다.
  37. ^ a b 클록스 외 연구진(1993)
  38. ^ Kloks & Bodlaender (1992년); Gustedt (1993년)
  39. ^ Garbe(1995)는 이 결과를 Ton Kloks의 1993년 박사 논문으로 인정한다. Garbe의 구간 순서 비교 그래프에 대한 다항식 시간 알고리즘은 어떤 화음 그래프가 이 유형의 비교가능성 그래프여야 하기 때문에 이 결과를 일반화한다.
  40. ^ 수찬&토딘카(2007)
  41. ^ Feige, Hajiahayi & Lee(2005년).
  42. ^ a b 로버트슨 & 시모어(2004년).
  43. ^ Vienstock 외 연구진(1991);Diestel(1995); Cattell, Dinneen & Fells(1996).
  44. ^ a b 키너슬리(1992);다카하시, 우에노&카지타니(1994), 보들라엔더(1998), 페이지 8.
  45. ^ Kinnersley & Langston(1994년).
  46. ^ 데메인, 하지아헤이 & 카와라바야시(2005년).
  47. ^ 버지(1967년).
  48. ^ 로페즈 앤 로(1980).
  49. ^ a b 펠로우즈 & 랭스턴(1989년).
  50. ^ 뫼링(1990);페레이라 & 송(1992년).
  51. ^ 흐리니(2003년).
  52. ^ 수더만(2004년).
  53. ^ 듀모비치 외 (2008).
  54. ^ 듀모비치, 모린 & 우드(2003년).
  55. ^ a b Bodlaender, Gustedt & Telle(1998년).
  56. ^ 밀러(1956년).
  57. ^ 크네이스 외 (2005);비외르클룬드 & 허스펠트(2008).

참조