Regularity and locality in \(k\)-terminal graphs

DOI10.1016/0166-218X(94)90025-6zbMath0822.68084MaRDI QIDQ1336630

Sanjeev Mahajan, Joseph G. Peters

Publication date: 28 November 1994

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

zbMATH Keywords

linear-time algorithmparse tree\(k\)-terminal recursive graphsregular graph properties

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Characterization and Recognition of Partial 3-Trees
• Complexity of Finding Embeddings in a k-Tree
• Linear-time computability of combinatorial problems on series-parallel graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

Related Items (6)

Algorithmic uses of the Feferman-Vaught theorem ⋮ Matchability and \(k\)-maximal matchings ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Efficiently parallelizable problems on a class of decomposable graphs ⋮ Definability equals recognizability of partial 3-trees ⋮ Myhill-Nerode Methods for Hypergraphs

This page was built for publication: Regularity and locality in \(k\)-terminal graphs