Partitioned probe comparability graphs

DOI10.1016/J.TCS.2008.01.038MaRDI QIDQ924151zbMATH OpenOpenAlexFDO

Authors David B. Chandler, Ton Kloks, Sheng-Lung Peng, Maw-Shang Chang, Jiping Liu

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 graphspermutation graphscomparability graphsprobe graphsgraph recognition algorithms

Mathematics Subject Classification ID

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

Recommendations

• Partitioned Probe Comparability Graphs
• Theory and Applications of Models of Computation
• On probe permutation graphs
• Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs
• Probe Ptolemaic Graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 5158503 (Why is no real title available?)
• scientific article; zbMATH DE number 1554932 (Why is no real title available?)
• scientific article; zbMATH DE number 2119749 (Why is no real title available?)
• scientific article; zbMATH DE number 1439437 (Why is no real title available?)
• A polynomial time recognition algorithm for probe interval graphs
• Algorithm Theory - SWAT 2004
• Chordal probe graphs (extended abstract)
• Comparability graphs and a new matroid
• Computing and Combinatorics
• Graph Sandwich Problems
• Matrix multiplication via arithmetic progressions
• Modular decomposition and transitive orientation
• On probe interval graphs
• Probe Matrix Problems: Totally Balanced Matrices
• Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs
• Recognizing Chordal Probe Graphs and Cycle-Bicolorable Graphs
• STACS 2005
• The complexity of comparability graph recognition and coloring
• Theory and Applications of Models of Computation
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Two tricks to triangulate chordal probe graphs in polynomial time

Cited in

(14)

• Probe Ptolemaic Graphs
• The \((k,\ell)\) \textsc{unpartitioned probe} problem NP-complete versus polynomial dichotomy
• Graph partitioning applied to the logic testing of combinational circuits
• Two tricks to triangulate chordal probe graphs in polynomial time
• Recognition of probe proper interval graphs
• Probe threshold and probe trivially perfect graphs
• Recognition of Probe Ptolemaic Graphs
• Computing and Combinatorics
• Recognition of Probe Cographs and Partitioned Probe Distance Hereditary Graphs
• Block-graph width
• Theory and Applications of Models of Computation
• Partitioned Probe Comparability Graphs
• An adjacency labeling scheme based on a decomposition of trees into caterpillars
• The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs

This page was built for publication: Partitioned probe comparability graphs

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