Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
From MaRDI portal
Publication:3204040
DOI10.1016/0196-6774(90)90013-5zbMath0716.68042OpenAlexW2159366821WikidataQ59568068 ScholiaQ59568068MaRDI QIDQ3204040
Publication date: 1990
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(90)90013-5
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)
Related Items (63)
Fast Algorithms for Join Operations on Tree Decompositions ⋮ A polynomial time algorithm for strong edge coloring of partial \(k\)-trees ⋮ The QAP-polytope and the graph isomorphism problem ⋮ Subexponential Time Algorithms for Finding Small Tree and Path Decompositions ⋮ Sequential and parallel algorithms for embedding problems on classes of partial k-trees ⋮ A parallel algorithm for edge-coloring partial k-trees ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ On the complexity of graph reconstruction ⋮ An improved isomorphism test for bounded-tree-width graphs ⋮ MSOL partitioning problems on graphs of bounded treewidth and clique-width ⋮ Edge-colouring and total-colouring chordless graphs ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Filtering graphs to check isomorphism and extracting mapping by using the conductance electrical model ⋮ Polynomial time algorithms for variants of graph matching on partial \(k\)-trees ⋮ Cleaning interval graphs ⋮ Two-closure of rank \(3\) groups in polynomial time ⋮ Isomorphism Testing Parameterized by Genus and Beyond ⋮ Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth ⋮ Practical graph isomorphism. II. ⋮ Confronting intractability via parameters ⋮ Graphs whose complement and square are isomorphic ⋮ The Space Complexity of k-Tree Isomorphism ⋮ Algorithms for finding distance-edge-colorings of graphs ⋮ Line graphs of bounded clique-width ⋮ Classifying \(k\)-edge colouring for \(H\)-free graphs ⋮ Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$ ⋮ Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size ⋮ Polynomial-time algorithm for isomorphism of graphs with clique-width at most three ⋮ Grammatical inference of directed acyclic graph languages with polynomial time complexity ⋮ Monadic second-order evaluations on tree-decomposable graphs ⋮ Tree decomposition and discrete optimization problems: a survey ⋮ Partitioning graphs of supply and demand ⋮ Parameterized graph cleaning problems ⋮ Colored hypergraph isomorphism is fixed parameter tractable ⋮ Complexity of path-forming games ⋮ Two feedback problems for graphs with bounded tree-width ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Chromatic index of graphs with no cycle with a unique chord ⋮ Generalized median graphs and applications ⋮ Efficient frequent connected subgraph mining in graphs of bounded tree-width ⋮ The isomorphism problem for \(k\)-trees is complete for logspace ⋮ Restricted space algorithms for isomorphism on bounded treewidth graphs ⋮ Unnamed Item ⋮ Vertex disjoint paths on clique-width bounded graphs ⋮ Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds ⋮ Approximability of partitioning graphs with supply and demand ⋮ Graph isomorphism restricted by lists ⋮ Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width ⋮ Optimization and Recognition for K 5-minor Free Graphs in Linear Time ⋮ Recognizing generalized Sierpiński graphs ⋮ Efficient Pattern Matching on Graph Patterns of Bounded Treewidth ⋮ Algorithms for generalized vertex-rankings of partial k-trees ⋮ A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES ⋮ Some further development on the eigensystem approach for graph isomorphism detection ⋮ Revising Johnson's table for the 21st century ⋮ Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs ⋮ Computational Complexity of Computing Symmetries in Finite-Domain Planning ⋮ Classical symmetries and the quantum approximate optimization algorithm ⋮ Counting \(H-\)colorings of partial \(k-\)trees ⋮ Exact algorithms for intervalizing coloured graphs ⋮ Canonisation and Definability for Graphs of Bounded Rank Width
This page was built for publication: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
