Minimal Oriented Graphs of Diameter 2 | Zendy

Nancy Lawson | Zendy; Mukkai S. Krishnamoorthy | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Minimal Oriented Graphs of Diameter 2

Author(s) -

Nancy Lawson,

Mukkai S. Krishnamoorthy

Publication year - 1998

Publication title -

graphs and combinatorics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.59

H-Index - 40

eISSN - 1435-5914

pISSN - 0911-0119

DOI - 10.1007/s003730050022

Subject(s) - combinatorics , mathematics , bridge (graph theory) , matrix (chemical analysis) , set (abstract data type) , decision problem , discrete mathematics , algorithm , computer science , medicine , materials science , composite material , programming language

Gate matrix layout is an NP-complete combinatorial problem. The related fixed-parameter decision problem has been thoroughly studied for small values of k in recent years. We chose to investigate a more difficult circular version of the fixed-parameter decision problem. We have identified a major group of obstructions to the circular 3-track layout problem. These obstructions all contain a bridge which separates sufficiently large subgraphs; they are called the bridge obstructions. The complete set of circular-3-GML bridge obstructions contains 336 graphs.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research