A labeling algorithm to recognize a line digraph and output its root graph
From MaRDI portal
Publication:1163377
DOI10.1016/0020-0190(82)90080-1zbMath0483.68062OpenAlexW2077380997WikidataQ56388861 ScholiaQ56388861MaRDI QIDQ1163377
Publication date: 1982
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(82)90080-1
Related Items
On some complexity properties of N-free posets and posets with bounded decomposition diameter ⋮ On finding the jump number of a partial order by substitution decomposition ⋮ N-free posets as generalizations of series-parallel posets ⋮ Reconstructing a graph from its arc incidence graph ⋮ Parallel \(N\)-free order recognition ⋮ New results and open problems in line graphs ⋮ Dominoes ⋮ The forbidden minor characterization of line-search antimatroids of rooted digraphs ⋮ Characterization of classical graph classes by weighted clique graphs ⋮ Transitive closure for restricted classes of partial orders ⋮ Parallel interval order recognition and construction of interval representations ⋮ \(N\)-free orders and minimal interval extensions ⋮ Review of properties of different precedence graphs for scheduling problems ⋮ Minimizing completion time for a class of scheduling problems ⋮ Minimizing the jump number for partially ordered sets: A graph-theoretic approach ⋮ Optimal constructions of reversible digraphs ⋮ On Page Number of N-free Posets ⋮ An algorithm for minimizing setups in precedence constrained scheduling
Cites Work
