On probe permutation graphs

DOI10.1016/j.dam.2008.08.017zbMath1211.05035OpenAlexW2059857922MaRDI QIDQ967305

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

Publication date: 28 April 2010

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

Full work available at URL: https://doi.org/10.1016/j.dam.2008.08.017

zbMATH Keywords

treewidthmodular decompositionpermutation graphsprobe graphsminimum fill-inweakly chordal graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

An adjacency labeling scheme based on a decomposition of trees into caterpillars ⋮ On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity ⋮ The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy ⋮ On the probe problem for \((r,\ell )\)-well-coveredness ⋮ Recognition of Probe Ptolemaic Graphs ⋮ Block-graph width ⋮ On the complete width and edge clique cover problems ⋮ Characterizing and recognizing probe block graphs ⋮ Probe interval and probe unit interval graphs on superclasses of cographs

Cites Work

• Characterizations of strongly chordal graphs
• Slim graphs
• On slim graphs, even pairs, and star-cutsets
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On probe interval graphs
• Modular decomposition and transitive orientation
• Listing all potential maximal cliques of a graph
• Chordal probe graphs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Listing all Minimal Separators of a Graph
• Treewidth and Pathwidth of Permutation Graphs
• Algorithm Theory - SWAT 2004
• Transitiv orientierbare Graphen
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Computing and Combinatorics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On probe permutation graphs