Graph isomorphism restricted by lists (Q5918143)

scientific article; zbMATH DE number 7318687

Language	Label	Description	Also known as
English	Graph isomorphism restricted by lists	scientific article; zbMATH DE number 7318687

Statements

instance of

scholarly article

0 references

title

Graph isomorphism restricted by lists (English)

0 references

0 references

0 references

0 references

Theoretical Computer Science

0 references

publication date

9 March 2021

0 references

full work available at URL

https://arxiv.org/abs/1607.03918

0 references

zbMATH Keywords

graph isomorphism problem

0 references

restricted computational problem

0 references

polynomial-time algorithms

0 references

NP-completeness

0 references

bounded treewidth

0 references

bounded degree graphs

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Complexity of Finding Embeddings in a <i>k</i>-Tree

0 references

A linear-time algorithm for testing the truth of certain quantified Boolean formulas

0 references

Isomorphism problem for a class of point-symmetric structures

0 references

Graph isomorphism in quasipolynomial time [extended abstract]

0 references

Induced minor free graphs: isomorphism and clique-width

0 references

On the Complexity of Covering Vertices by Faces in a Planar Graph

0 references

Precoloring extension. I: Interval graphs

0 references

Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees

0 references

Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

0 references

An optimal lower bound on the number of variables for graph identification

0 references

List H-coloring a graph by removing few vertices

0 references

On testing isomorphism of permutation graphs

0 references

Q4186367

0 references

A Theoretical Analysis of Various Heuristics for the Graph Isomorphism Problem

0 references

Complement reducible graphs

0 references

A Combinatorial Decomposition Theory

0 references

Decomposition of Directed Graphs

0 references

Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy

0 references

On Structural Parameterizations of Graph Motif and Chromatic Number

0 references

3-connected Planar Graph Isomorphism is in Log-space

0 references

Q4038721

0 references

On-Line Planarity Testing

0 references

Canonizing Graphs of Bounded Tree Width in Logspace

0 references

Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks

0 references

On the Complexity of Timetable and Multicommodity Flow Problems

0 references

Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs

0 references

3-connected reduction for regular graph covers

0 references

On the complexity of reconstructing H-free graphs from their Star Systems

0 references

Transitiv orientierbare Graphen

0 references

Structure theorem and isomorphism test for graphs with excluded topological subgraphs

0 references

Descriptive Complexity, Canonisation, and Definable Graph Structure Theory

0 references

Q4472293

0 references

Q4828516

0 references

Q3875946

0 references

Dividing a Graph into Triconnected Components

0 references

Q4148000

0 references

An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

0 references

$A\,V^ 2$ algorithm for determining isomorphism of planar graphs

0 references

$O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs

0 references

Automorphism Groups of Geometrically Represented Graphs

0 references

Treewidth. Computations and approximations

0 references

The Isomorphism Problem for k-Trees Is Complete for Logspace

0 references

Interval Graphs: Canonical Representations in Logspace

0 references

An Incremental Linear-Time Algorithm for Recognizing Interval Graphs

0 references

Algorithmic complexity of list colorings

0 references

Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs

0 references

Le problème d'étoiles pour graphes est NP-complèt

0 references

Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth

0 references

Some NP-Complete Problems Similar to Graph Isomorphism

0 references

A Linear Time Algorithm for Deciding Interval Graph Isomorphism

0 references

Isomorphism of graphs of bounded valence can be tested in polynomial time

0 references

A note on the graph isomorphism counting problem

0 references

Modular decomposition and transitive orientation

0 references

Q3670594

0 references

Isomorphism on Subgraph-Closed Graph Classes: A Complexity Dichotomy and Intermediate Graph Classes

0 references

Reduction Techniques for Graph Isomorphism in the Context of Width Parameters

0 references

The isomorphism problem for classes of graphs closed under contraction

0 references

Undirected connectivity in log-space

0 references

The complexity of satisfiability problems

0 references

Graph isomorphism is in the low hierarchy

0 references

Isomorphism of (mis)Labeled Graphs

0 references

Towards an Isomorphism Dichotomy for Hereditary Graph Classes

0 references

On Comparability and Permutation Graphs

0 references

Q3268317

0 references

Q5524326

0 references

Tractabilities and intractabilities on geometric intersection graphs

0 references

Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs

0 references

Q4135588

0 references

Counting unlabelled three-connected and homeomorphically irreducible two- connected graphs

0 references

On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler

0 references

Identifiers

zbMATH Open document ID

1497.68385

0 references

DOI

10.1016/j.tcs.2021.01.027

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:5918143