On the complexity of the identifiable subgraph problem

DOI10.1016/j.dam.2014.10.021zbMath1306.05164MaRDI QIDQ2255039

Martin Milanič, Marcin Kaminski

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

bipartite graph; matching; polynomial algorithm; topological minor; identifiable graph; strongly cyclic graph

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

On the complexity of the identifiable subgraph problem, revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structural identifiability in low-rank matrix factorization
• Graph minors. XIII: The disjoint paths problem
• Resilience and optimization of identifiable bipartite graphs
• Parametrized complexity theory.
• Document clustering using nonnegative matrix factorization
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Learning the parts of objects by non-negative matrix factorization
• Finding topological subgraphs is fixed-parameter tractable
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth