Solving Undirected Graph Problems on VLSI

DOI10.1137/0214040MaRDI QIDQ3680291zbMATH OpenOpenAlexFDO

Authors Susanne E. Hambrusch, Janos Simon

Publication date 1985

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0214040

zbMATH Keywords

connected component probleminformation flowKolmogorov complexitylower boundnetworksoptimal algorithmundirected graphVLSI complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Recommendations

• scientific article; zbMATH DE number 3860407
• New fast parallel algorithm for the connected component problem and its VLSI implementation
• The VLSI Complexity of Selected Graph Problems
• scientific article; zbMATH DE number 3905849
• scientific article; zbMATH DE number 3930349

Cited in

(9)

• Representations of graphs and networks (coding, layouts and embeddings)
• Communication complexity and combinatorial lattice theory
• Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments
• scientific article; zbMATH DE number 3860407 (Why is no real title available?)
• New fast parallel algorithm for the connected component problem and its VLSI implementation
• The VLSI Complexity of Selected Graph Problems
• On VLSI layouts of the star graph and related networks
• Minimum vertex cover, distributed decision-making, and communication complexity
• A framework for solving VLSI graph layout problems

This page was built for publication: Solving Undirected Graph Problems on VLSI

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