Block-graph width

DOI10.1016/j.tcs.2010.10.041zbMath1221.05274OpenAlexW2113596268MaRDI QIDQ534563

Maw-Shang Chang, Sheng-Lung Peng, Ling-Ju Hung, Ton Kloks

Publication date: 18 May 2011

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

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

zbMATH Keywords

block graphsparameterized algorithmsprobe graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

An adjacency labeling scheme based on a decomposition of trees into caterpillars ⋮ Good characterizations and linear time recognition for 2-probe block graphs ⋮ On the complete width and edge clique cover problems ⋮ Characterizing and recognizing probe block graphs ⋮ On some FPT problems without polynomial Turing compressions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• Partitioned probe comparability graphs
• On probe permutation graphs
• On probe interval graphs
• Letter graphs and well-quasi-order by induced subgraphs
• Upper bounds to the clique width of graphs
• Rank-width and vertex-minors
• Algorithms on Strings, Trees and Sequences
• Graph Classes: A Survey
• Graph Sandwich Problems
• A Characterization of Certain Ptolemaic Graphs
• Depth-First Search and Linear Graph Algorithms
• Ordering by Divisibility in Abstract Algebras
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Block-graph width