An NP-completeness result of edge search in graphs
DOI10.1007/S00373-013-1287-YzbMATH Open1293.05367OpenAlexW2075281130MaRDI QIDQ2014718FDOQ2014718
Authors: Tatjana Gerzen 
Publication date: 16 June 2014
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00373-013-1287-y
Recommendations
- NP-completeness results for edge modification problems
- Edge search in graphs and hypergraphs of bounded rank
- scientific article; zbMATH DE number 3889547
- NP-completeness of some edge-disjoint paths problems
- Edge search in hypergraphs
- NP-completeness of edge-colouring some restricted graphs
- On the algorithmic complexity of edge total domination
- The complexity of searching a graph
- Edge Search Number of Cographs in Linear Time
- Lower Bounds on Edge Searching
Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Reliability, testing and fault tolerance of networks and computer systems (68M15)
Cites Work
- Reducibility among combinatorial problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Pooling designs and nonadaptive group testing. Important tools for DNA sequencing.
- Title not available (Why is that?)
- A probabilistic upper bound for the edge identification complexity of graphs
- Searching for an edge in a graph with restricted test sets
- Edge search in graphs with restricted test sets
- Title not available (Why is that?)
- On a group testing problem: characterization of graphs with 2-complexity and maximum number of edges
- Title not available (Why is that?)
Cited In (5)
- On a group testing problem: characterization of graphs with 2-complexity and maximum number of edges
- Edge search number of cographs
- On the hardness of solving edge matching puzzles as SAT or CSP problems
- Searching for an edge in a graph with restricted test sets
- NP-completeness for minimizing maximum edge length in grid embeddings
This page was built for publication: An NP-completeness result of edge search in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2014718)
