An NP-completeness result of edge search in graphs

DOI10.1007/S00373-013-1287-YMaRDI QIDQ2014718zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

NP-completenessgroup testing problemcombinatorial searchedge search

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 3662840 (Why is no real title available?)
• scientific article; zbMATH DE number 41347 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 819134 (Why is no real title available?)
• scientific article; zbMATH DE number 823957 (Why is no real title available?)
• A probabilistic upper bound for the edge identification complexity of graphs
• Edge search in graphs with restricted test sets
• On a group testing problem: characterization of graphs with 2-complexity and maximum number of edges
• Pooling designs and nonadaptive group testing. Important tools for DNA sequencing.
• Reducibility among combinatorial problems
• Searching for an edge in a graph with restricted test sets

Cited in

(5)

• Edge search number of cographs
• NP-completeness for minimizing maximum edge length in grid embeddings
• On the hardness of solving edge matching puzzles as SAT or CSP problems
• On a group testing problem: characterization of graphs with 2-complexity and maximum number of edges
• Searching for an edge in a graph with restricted test sets

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)