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
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
