An efficient algorithm for finding a two-pair, and its applications

DOI10.1016/0166-218X(91)90033-SMaRDI QIDQ1814097zbMATH OpenOpenAlexFDO

Authors S. R. Arikati, C. Pandu Rangan

Publication date 25 June 1992

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218x(91)90033-s

zbMATH Keywords

algorithmchordless pathcomputational geometryweakly triangulated graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10)

Review text

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.

Recommendations

• An efficient algorithm for the bipartite matching problem
• An algorithm for finding homogeneous pairs
• scientific article; zbMATH DE number 2081005
• scientific article; zbMATH DE number 4014451
• Parameterized and approximation algorithms for finding two disjoint matchings
• Parameterized and Approximation Algorithms for Finding Two Disjoint Matchings
• scientific article; zbMATH DE number 1305400
• Efficient algorithms for Petersen's matching theorem
• Faster algorithm for finding maximum 1-restricted simple 2-matchings
• On Nagata's pairwise algorithm

Cites work

• Covering orthogonal polygons with star polygons: The perfect graph approach
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• Perfect Graphs and Orthogonally Convex Covers

Cited in

(14)

• Algorithms for interval catch digraphs
• Path parity and perfection
• Algorithms for weakly triangulated graphs
• Linear layouts of weakly triangulated graphs
• Symmetric graph-theoretic roles of two-pairs and chords of cycles
• Gender-aware facility location in multi-gender world
• Organizing the atoms of the clique separator decomposition into an atom tree
• scientific article; zbMATH DE number 4117882 (Why is no real title available?)
• A separator-based method for generating weakly chordal graphs
• An algorithm for finding homogeneous pairs
• Verification of a certificate for weakly chordal graphs
• Minimal triangulations of graphs: a survey
• A vertex incremental approach for maintaining chordality
• A new characterization of HH-free graphs

This page was built for publication: An efficient algorithm for finding a two-pair, and its applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1814097)