A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
From MaRDI portal
Publication:2264685
DOI10.1016/0020-0190(73)90029-XzbMath0274.05116OpenAlexW2014287896WikidataQ56388854 ScholiaQ56388854MaRDI QIDQ2264685
Publication date: 1973
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(73)90029-x
Related Items (89)
Circumferences of 3-connected claw-free graphs ⋮ Circumferences of 3-connected claw-free graphs. II. ⋮ Degree distribution and assortativity in line graphs of complex networks ⋮ A twelve vertex theorem for 3-connected claw-free graphs ⋮ Even and odd pairs in linegraphs of bipartite graphs ⋮ Reconstructibility of Matroid Polytopes ⋮ On equistable, split, CIS, and related classes of graphs ⋮ Recognizing intersection graphs of linear uniform hypergraphs ⋮ Degree and neighborhood conditions for Hamiltonicity of claw-free graphs ⋮ The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs ⋮ Color-line and proper color-line graphs ⋮ Polyhedral characterizations and perfection of line graphs ⋮ Complexity classification of the edge coloring problem for a family of graph classes ⋮ Reconstructing a graph from its arc incidence graph ⋮ Fast recognition of doubled graphs ⋮ Triangle packings and transversals of some \(K_{4}\)-free graphs ⋮ Biclique graphs of interval bigraphs ⋮ Generalized line graphs: Cartesian products and complexity of recognition ⋮ On the parameterized complexity of the acyclic matching problem ⋮ A characterization of line graphs that are squares of graphs ⋮ ILIGRA: an efficient inverse line graph algorithm ⋮ New results and open problems in line graphs ⋮ On stable cutsets in line graphs ⋮ A dynamic algorithm for line graph recognition ⋮ Exact algorithms for finding longest cycles in claw-free graphs ⋮ Linear algorithms to recognize outerplanar and maximal outerplanar graphs ⋮ On weighted efficient total domination ⋮ Intersection graph of maximal stars ⋮ Packing cycles exactly in polynomial time ⋮ Finding induced paths of given parity in claw-free graphs ⋮ Dominoes ⋮ On claw-free \(t\)-perfect graphs ⋮ Classes of perfect graphs ⋮ Minimizing the Hamming distance between a graph and a line-graph to discover the topology of an electrical network ⋮ Clique family inequalities for the stable set polytope of quasi-line graphs. ⋮ Complexity of independent set reconfigurability problems ⋮ On the hardness of recognizing triangular line graphs ⋮ On graphs with no induced subdivision of \(K_4\) ⋮ Graphs vertex-partitionable into strong cliques ⋮ Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs ⋮ Fair allocation of indivisible items with conflict graphs ⋮ Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs ⋮ Finding a smallest odd hole in a claw-free graph using global structure ⋮ Recognizing \(k\)-path graphs ⋮ A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. ⋮ Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs ⋮ Equistable simplicial, very well-covered, and line graphs ⋮ The (theta, wheel)-free graphs. IV: Induced paths and cycles ⋮ Forests and trees among Gallai graphs ⋮ Hamiltonicity of claw-free graphs and Fan-type conditions ⋮ The clique-transversal set problem in claw-free graphs with degree at most 4 ⋮ On stable cutsets in claw-free graphs and planar graphs ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Coloring perfect graphs with no balanced skew-partitions ⋮ Line graphs of bounded clique-width ⋮ An incremental polynomial time algorithm to enumerate all minimal edge dominating sets ⋮ Decomposing Berge graphs and detecting balanced skew partitions ⋮ A search strategy for the elementary cycles of a directed graph ⋮ Chvátal-Erdős type conditions for Hamiltonicity of claw-free graphs ⋮ A finite characterization and recognition of intersection graphs of hypergraphs with rank at most 3 and multiplicity at most 2 in the class of threshold graphs ⋮ Line graph links ⋮ Local search algorithms for finding the Hamiltonian completion number of line graphs ⋮ Edge intersection graphs of linear 3-uniform hypergraphs ⋮ Edge intersection graphs of linear 3-uniform hypergraphs ⋮ Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs ⋮ The edge Hamiltonian path problem is NP-complete for bipartite graphs ⋮ The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ Induced Disjoint Paths in Claw-Free Graphs ⋮ Basic perfect graphs and their extensions ⋮ Computing Sharp 2-Factors in Claw-Free Graphs ⋮ Computing sharp 2-factors in claw-free graphs ⋮ Finding the root graph through minimum edge deletion ⋮ A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs ⋮ Claw-Free $t$-Perfect Graphs Can Be Recognized in Polynomial Time ⋮ Strong cliques in diamond-free graphs ⋮ Clique-perfectness of complements of line graphs ⋮ On minimal forbidden subgraph characterizations of balanced graphs ⋮ Detecting strong cliques ⋮ The parameterized complexity of the induced matching problem ⋮ Hypercube emulation of interconnection networks topologies ⋮ Algorithm for the optimal reconstruction of a digraph ⋮ Combinatorial optimization with 2-joins ⋮ Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition ⋮ An algorithm to recognize a middle graph ⋮ A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs ⋮ Independent point-set domination in line graphs ⋮ Approximation algorithms for clique transversals on some graph classes ⋮ Strong cliques and equistability of EPT graphs
Cites Work
This page was built for publication: A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
