On the np-completeness of certain network testing problems

DOI10.1002/NET.3230140102MaRDI QIDQ3315441zbMATH OpenOpenAlexFDO

Authors

Publication date 1984

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.3230140102

zbMATH Keywords

communication networkedge coloringmaximum matchingNP-hardundirected graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of graph theory to circuits and networks (94C15)

Recommendations

• scientific article; zbMATH DE number 3848612
• Some complexity results about packet radio networks (Corresp.)
• The complexity of path coloring and call scheduling
• A minimax assignment problem in treelike communication networks
• NP-completeness of some edge-disjoint paths problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the np-completeness of certain network testing problems

Cited in

(14)

• Maximal selection in tandem networks with symmetric hearing range
• NP-completeness of some generalizations of the maximum matching problem
• A pie allocation among sharing groups
• Donation center location problem
• Maximum induced matching algorithms via vertex ordering characterizations
• On the np-completeness of certain network testing problems
• Maximum induced matching algorithms via vertex ordering characterizations
• Parameterized complexity of perfectly matched sets
• Induced matchings in strongly biconvex graphs and some algebraic applications
• Reception capacity: definitions, game theory and hardness
• The efficiency of AC graphs
• A lower bound on the period length of a distributed scheduler
• Parameterized complexity of perfectly matched sets
• The complexity of finding uniform emulations on paths and ring networks

This page was built for publication: On the np-completeness of certain network testing problems

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