On the complexity of the identifiable subgraph problem

DOI10.1016/J.DAM.2014.10.021MaRDI QIDQ2255039zbMATH OpenOpenAlexFDO

Authors Martin Milanič, Marcin Kamiński

Publication date 6 February 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2014.10.021

zbMATH Keywords

matchingbipartite graphpolynomial algorithmtopological minoridentifiable graphstrongly cyclic graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On the complexity of the identifiable subgraph problem, revisited
• Resilience and optimization of identifiable bipartite graphs
• The complexity of the identifying code problem in restricted graph classes
• Complexity of finding maximum regular induced subgraphs with prescribed degree
• Complexity of finding maximum regular induced subgraphs with prescribed degree

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Application of logic to combinatorial sequences and their recurrence relations
• Document clustering using nonnegative matrix factorization
• Finding topological subgraphs is fixed-parameter tractable
• Graph minors. XIII: The disjoint paths problem
• Graph theory
• Learning the parts of objects by non-negative matrix factorization
• Parametrized complexity theory.
• Resilience and optimization of identifiable bipartite graphs
• Structural identifiability in low-rank matrix factorization
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The tree- and clique-width of bipartite graphs in special classes

Cited in

(7)

• On the Distance Identifying Set Meta-Problem and Applications to the Complexity of Identifying Problems on Graphs
• A probabilistic upper bound for the edge identification complexity of graphs
• The complexity of regular subgraph recognition
• An optimal lower bound on the number of variables for graph identification
• Resilience and optimization of identifiable bipartite graphs
• On Graph Identification Problems and the Special Case of Identifying Vertices Using Paths
• On the complexity of the identifiable subgraph problem, revisited

This page was built for publication: On the complexity of the identifiable subgraph problem

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