Partitioned probe comparability graphs

DOI10.1016/j.tcs.2008.01.038zbMath1145.68037OpenAlexW2048261494MaRDI QIDQ924151

Sheng-Lung Peng, David B. Chandler, Ton Kloks, Ji Ping Liu, Maw-Shang Chang

Publication date: 28 May 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.01.038

zbMATH Keywords

cocomparability graphscomparability graphspermutation graphsprobe graphsgraph recognition algorithms

Mathematics Subject Classification ID

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

Related Items (6)

An adjacency labeling scheme based on a decomposition of trees into caterpillars ⋮ Recognition of probe proper interval graphs ⋮ Recognition of Probe Ptolemaic Graphs ⋮ Block-graph width ⋮ The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs ⋮ Probe threshold and probe trivially perfect graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Comparability graphs and a new matroid
• The complexity of comparability graph recognition and coloring
• On probe interval graphs
• Modular decomposition and transitive orientation
• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
• Graph Sandwich Problems
• Algorithm Theory - SWAT 2004
• Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs
• Probe Matrix Problems: Totally Balanced Matrices
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• STACS 2005
• Computing and Combinatorics
• Theory and Applications of Models of Computation
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Partitioned probe comparability graphs