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
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
