Combinatorics and algorithms for quasi-chain graphs

DOI10.1007/978-3-030-79987-8_4OpenAlexW3184216788MaRDI QIDQ5918620

Vadim V. Lozin, Bogdan Alecu, Aistis Atminas, Dmitriy S. Malyshev

Publication date: 22 March 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2104.04471

zbMATH Keywords

polynomial-time algorithmimplicit representationbipartite chain graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Related Items (1)

Combinatorics and algorithms for quasi-chain graphs

Cites Work

• Unnamed Item
• Pattern matching for permutations
• Implicit representations and factorial properties of graphs
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Patterns in permutations and words.
• Satgraphs and independent domination. I
• Domination in convex and chordal bipartite graphs
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• Alternating cycle-free matchings
• Letter graphs and well-quasi-order by induced subgraphs
• Efficient graph representations
• The maximum edge biclique problem is NP-complete
• On maximum induced matchings in bipartite graphs
• The speed of hereditary properties of graphs
• HAMILTONian circuits in chordal bipartite graphs
• Bounds for graph regularity and removal lemmas
• Bipartite induced subgraphs and well-quasi-ordering
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• Forbidden induced bipartite graphs
• Implicat Representation of Graphs
• Regularity lemmas for stable graphs
• Difference graphs
• The NP-completeness column: An ongoing guide

This page was built for publication: Combinatorics and algorithms for quasi-chain graphs