On the np-completeness of certain network testing problems

DOI10.1002/NET.3230140102zbMATH Open0532.94017OpenAlexW2057904195MaRDI QIDQ3315441FDOQ3315441

Authors:

Publication date: 1984

Published in: Networks (Search for Journal in Brave)

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

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

zbMATH Keywords

communication networkNP-hardedge coloringundirected graphmaximum matching

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On the np-completeness of certain network testing problems

Cited In (13)

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