An efficient algorithm for finding a two-pair, and its applications (Q1814097): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Jörgen Bang-Jensen / rank | |||
Property / reviewed by | |||
Property / reviewed by: Jörgen Bang-Jensen / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3328583 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Perfect Graphs and Orthogonally Convex Covers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Covering orthogonal polygons with star polygons: The perfect graph approach / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3799261 / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0166-218x(91)90033-s / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2024353971 / rank | |||
Normal rank |
Latest revision as of 11:54, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An efficient algorithm for finding a two-pair, and its applications |
scientific article |
Statements
An efficient algorithm for finding a two-pair, and its applications (English)
0 references
25 June 1992
0 references
A two-pair in an undirected graph \(G\) is a pair of vertices \(u\) and \(v\) such that every chordless path between \(u\) and \(v\) has length 2. This note presents an efficient \(O(| V|| E|)\) algorithm to decide if a given graph \(G\) has a two-pair and output one if it exists. The authors discuss applications of this algorithm and mention that this implies new and faster algorithms for the following four problems on weakly triangulated graphs: minimum clique cover, maximum clique, maximum independent set, and minimum colouring. Each of these problems can be solved in time \(O(| V| T)\), where \(T\) is the time required to find a two-pair. Previous algorithms for these problems had complexity \(O(| V|^ 5)\). Hence this new algorithm implies an improvement by a factor \(| V|\). Applications to computational geometry are also discussed.
0 references
chordless path
0 references
algorithm
0 references
weakly triangulated graphs
0 references
computational geometry
0 references