Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
From MaRDI portal
Publication:3204040
DOI10.1016/0196-6774(90)90013-5zbMATH Open0716.68042DBLPjournals/jal/Bodlaender90OpenAlexW2159366821WikidataQ59568068 ScholiaQ59568068MaRDI QIDQ3204040FDOQ3204040
Authors: Hans L. Bodlaender 
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)
Cited In (67)
- A parallel algorithm for edge-coloring partial k-trees
- Fixed-point definability and polynomial time on chordal graphs and line graphs
- Computational Complexity of Computing Symmetries in Finite-Domain Planning
- Two-closure of rank \(3\) groups in polynomial time
- Constraint satisfaction, graph isomorphism, and the pebbling comonad
- Isomorphism Testing Parameterized by Genus and Beyond
- Title not available (Why is that?)
- Graph isomorphism restricted by lists
- Fast Algorithms for Join Operations on Tree Decompositions
- Polynomial-time algorithm for isomorphism of graphs with clique-width at most three
- Exact algorithms for intervalizing coloured graphs
- Classical symmetries and the quantum approximate optimization algorithm
- Optimization and Recognition for K 5-minor Free Graphs in Linear Time
- Practical graph isomorphism. II.
- Tree decomposition and discrete optimization problems: a survey
- Parameterized graph cleaning problems
- The QAP-polytope and the graph isomorphism problem
- Algorithms for generalized vertex-rankings of partial k-trees
- Complexity of path-forming games
- On the complexity of graph reconstruction
- Approximability of partitioning graphs with supply and demand
- Vertex disjoint paths on clique-width bounded graphs
- Grammatical inference of directed acyclic graph languages with polynomial time complexity
- Colorings with few colors: counting, enumeration and combinatorial bounds
- Polynomial time algorithms for variants of graph matching on partial \(k\)-trees
- Fixed-Parameter Tractability of Treewidth and Pathwidth
- Efficient frequent connected subgraph mining in graphs of bounded tree-width
- Restricted space algorithms for isomorphism on bounded treewidth graphs
- The isomorphism problem for \(k\)-trees is complete for logspace
- Algorithms for finding distance-edge-colorings of graphs
- Sequential and parallel algorithms for embedding problems on classes of partial k-trees
- Colored hypergraph isomorphism is fixed parameter tractable
- Chromatic index of graphs with no cycle with a unique chord
- Graphs of Bounded Treewidth Can Be Canonized in $\mbox{{\sf AC}$^1$}$
- Two feedback problems for graphs with bounded tree-width
- Title not available (Why is that?)
- A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
- Some further development on the eigensystem approach for graph isomorphism detection
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Line graphs of bounded clique-width
- An improved isomorphism test for bounded-tree-width graphs
- Generalized median graphs and applications
- Recognizing generalized Sierpiński graphs
- Efficient pattern matching on graph patterns of bounded treewidth
- Confronting intractability via parameters
- Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees
- Monadic second-order evaluations on tree-decomposable graphs
- Canonisation and Definability for Graphs of Bounded Rank Width
- Counting \(H-\)colorings of partial \(k-\)trees
- Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size
- Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
- Finding edge-disjoint paths in partial k-trees
- A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES
- Complexity-separating graph classes for vertex, edge and total colouring
- Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs
- Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width
- Cleaning interval graphs
- Classifying \(k\)-edge colouring for \(H\)-free graphs
- Filtering graphs to check isomorphism and extracting mapping by using the conductance electrical model
- Subexponential Time Algorithms for Finding Small Tree and Path Decompositions
- Colorings with few colors: counting, enumeration and combinatorial bounds
- Graphs whose complement and square are isomorphic
- Edge-colouring and total-colouring chordless graphs
- The Space Complexity of k-Tree Isomorphism
- Revising Johnson's table for the 21st century
- Partitioning graphs of supply and demand
- Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
This page was built for publication: Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3204040)
