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