A theorem on permutation graphs with applications

DOI10.1016/0020-0255(94)90001-9zbMath0803.05051OpenAlexW2019906874MaRDI QIDQ1328502

Gen-Huey Chen, Chang Wu Yu

Publication date: 26 July 1994

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: http://ntur.lib.ntu.edu.tw/bitstream/246246/154702/1/27.pdf

zbMATH Keywords

parallel algorithmscographspermutation graphssequential algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel recognition of complement reducible graphs and cotree construction
• Decomposing a set of points into chains, with applications to permutation and circle graphs
• Bipartite permutation graphs
• On domination problems for permutation and other graphs
• Finding a minimum independent dominating set in a permutation graph
• Complement reducible graphs
• Parallel Algorithm for Cograph Recognition with Applications
• Parallel algorithms for cographs and parity graphs with applications
• On Comparability and Permutation Graphs
• A Linear Recognition Algorithm for Cographs
• Domination in permutation graphs
• The NP-completeness column: an ongoing guide
• Parallel Merge Sort
• Orientations of circle graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs

This page was built for publication: A theorem on permutation graphs with applications