NLC₂-decomposition in polynomial time (extended abstract)

DOI10.1007/3-540-46784-X_12MaRDI QIDQ4944972zbMATH OpenFDO

Authors Öjvind Johansson

Publication date 22 May 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-46784-X_12

zbMATH Keywords

algorithmdecompositiondynamic programminglabelsvertex-labeled graphs

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• NLC\(_{2}\)-decomposition in polynomial time
• scientific article; zbMATH DE number 2044940
• \(k\)-NLC graphs and polynomial algorithms
• Polynomial decompositions in polynomial time
• General polynomial decomposition and the s-1-decomposition are NP-Hard
• An \(O(n^{lg\,k}\cdot 2^{n/2})\) time and \(O(k\cdot 2^{n/k})\) space algorithm for certain NP-complete problems
• scientific article; zbMATH DE number 1263306
• An O(n2) Algorithm for Undirected Split Decomposition
• On a polytime factorization algorithm for multilinear polynomials over \(\mathbb{F}_2\)
• scientific article; zbMATH DE number 3902038

Cited in

(5)

• \(k\)-NLC graphs and polynomial algorithms
• NLC-2 Graph Recognition and Isomorphism
• scientific article; zbMATH DE number 2044940 (Why is no real title available?)
• scientific article; zbMATH DE number 1472167 (Why is no real title available?)
• NLC\(_{2}\)-decomposition in polynomial time

This page was built for publication: \(\text{NLC}_2\)-decomposition in polynomial time (extended abstract)

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