An algorithm for finding homogeneous pairs

DOI10.1016/0166-218X(95)00090-EMaRDI QIDQ674438zbMATH OpenOpenAlexFDO

Authors Hazel Everett, Sulamita Klein, Bruce Reed

Publication date 9 November 1997

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

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

polynomial-time algorithmhomogeneous pair

Mathematics Subject Classification ID

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

Recommendations

• Algorithms for some \(H\)-join decompositions
• Algorithms for the homogeneous set sandwich problem
• An efficient algorithm for solving the homogeneous set sandwich problem
• The pair completion algorithm for the homogeneous set sandwich problem
• An efficient algorithm for finding a two-pair, and its applications

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3896983 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Bull-free Berge graphs are perfect
• Comparability graphs and a new matroid
• Depth-First Search and Linear Graph Algorithms
• Incremental modular decomposition
• Normal hypergraphs and the perfect graph conjecture
• \(P_ 4\)-trees and substitution decomposition

Cited in

(10)

• Computing pairings using x-coordinates only
• Coloring perfect graphs with no balanced skew-partitions
• A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants)
• An efficient algorithm for finding a two-pair, and its applications
• Counting List Matrix Partitions of Graphs
• The sandwich problem for decompositions and almost monotone properties
• Computing \(H\)-joins with application to 2-modular decomposition
• Claw-free graphs, skeletal graphs, and a stronger conjecture on \(\omega\), \(\Delta\), and \(\chi\)
• Graph parameters measuring neighbourhoods in graphs-bounds and applications
• Algorithms for some \(H\)-join decompositions

This page was built for publication: An algorithm for finding homogeneous pairs

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