A max \m, n \ algorithm for determining the graph H from its line graph G

Cites Work

Depth-First Search and Linear Graph Algorithms
Title not available (Why is that?)
The interchange graph of a finite graph

Cited In (89)

A characterization of line graphs that are squares of graphs
Strong cliques and equistability of EPT graphs
Circumferences of 3-connected claw-free graphs
On graphs with no induced subdivision of \(K_4\)
On equistable, split, CIS, and related classes of graphs
Hypercube emulation of interconnection networks topologies
On claw-free \(t\)-perfect graphs
Coloring perfect graphs with no balanced skew-partitions
On weighted efficient total domination
Packing cycles exactly in polynomial time
Detecting strong cliques
Strong cliques in diamond-free graphs
The edge Hamiltonian path problem is NP-complete for bipartite graphs
Dominoes
A twelve vertex theorem for 3-connected claw-free graphs
On stable cutsets in line graphs
Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
Exact algorithms for finding longest cycles in claw-free graphs
On the hardness of recognizing triangular line graphs
Even and odd pairs in linegraphs of bipartite graphs
Equistarable graphs and counterexamples to three conjectures on equistable graphs
Complexity of independent set reconfigurability problems
Generalized line graphs: Cartesian products and complexity of recognition
A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs
Linear algorithms to recognize outerplanar and maximal outerplanar graphs
Line graphs of bounded clique-width
Polyhedral characterizations and perfection of line graphs
A search strategy for the elementary cycles of a directed graph
Circumferences of 3-connected claw-free graphs. II.
Forests and trees among Gallai graphs
Equistable simplicial, very well-covered, and line graphs
Clique family inequalities for the stable set polytope of quasi-line graphs.
Decomposing Berge graphs and detecting balanced skew partitions
Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs
The parameterized complexity of the induced matching problem
Classes of perfect graphs
Degree and neighborhood conditions for Hamiltonicity of claw-free graphs
Complexity classification of the edge coloring problem for a family of graph classes
Recognizing \(k\)-path graphs
Parameterized complexity of induced graph matching on claw-free graphs
The clique-transversal set problem in claw-free graphs with degree at most 4
Reconstructing a graph from its arc incidence graph
Graphs vertex-partitionable into strong cliques
Degree distribution and assortativity in line graphs of complex networks
Computing Sharp 2-Factors in Claw-Free Graphs
ILIGRA: an efficient inverse line graph algorithm
A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.
An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
An algorithm to recognize a middle graph
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
Basic perfect graphs and their extensions
Combinatorial optimization with 2-joins
Line graph links
Claw-free \(t\)-perfect graphs can be recognized in polynomial time
Clique-perfectness of complements of line graphs
Edge intersection graphs of linear 3-uniform hypergraphs
On stable cutsets in claw-free graphs and planar graphs
Computing sharp 2-factors in claw-free graphs
Reconstructibility of matroid polytopes
Fast recognition of doubled graphs
Solving the weighted stable set problem in claw-free graphs via decomposition
Local search algorithms for finding the Hamiltonian completion number of line graphs
Recognizing intersection graphs of linear uniform hypergraphs
Chvátal-Erdős type conditions for Hamiltonicity of claw-free graphs
New results and open problems in line graphs
Hamiltonicity of claw-free graphs and Fan-type conditions
Fixed-point definability and polynomial time on chordal graphs and line graphs
The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness
Minimizing the Hamming distance between a graph and a line-graph to discover the topology of an electrical network
Approximation algorithms for clique transversals on some graph classes
Finding a smallest odd hole in a claw-free graph using global structure
A dynamic algorithm for line graph recognition
Finding the root graph through minimum edge deletion
On the parameterized complexity of the acyclic matching problem
A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
Edge intersection graphs of linear 3-uniform hypergraphs
Independent point-set domination in line graphs
Algorithm for the optimal reconstruction of a digraph
Induced disjoint paths in claw-free graphs
Color-line and proper color-line graphs
The (theta, wheel)-free graphs. IV: Induced paths and cycles
Triangle packings and transversals of some \(K_{4}\)-free graphs
On minimal forbidden subgraph characterizations of balanced graphs
Fair allocation of indivisible items with conflict graphs
Intersection graph of maximal stars
Stable sets in \(\{\mathrm{ISK4,wheel}\}\)-free graphs
Finding induced paths of given parity in claw-free graphs
Biclique graphs of interval bigraphs

This page was built for publication: A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G

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