Uniquely Restricted Matchings in Interval Graphs
From MaRDI portal
Publication:3130447
DOI10.1137/16M1074631zbMath1378.05137arXiv1604.07016OpenAlexW2483664717MaRDI QIDQ3130447
Dalu Jacob, Satyabrata Jana, Mathew C. Francis
Publication date: 22 January 2018
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1604.07016
interval graphuniquely restricted matchingproper interval graphbipartite permutation graphinterval nest digraphweak independent set
Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (5)
Parameterized complexity of perfectly matched sets ⋮ Degenerate matchings and edge colorings ⋮ On some hard and some tractable cases of the maximum acyclic matching problem ⋮ On the complexity of minimum maximal uniquely restricted matching ⋮ Domination number of an interval catch digraph family and its use for testing uniformity
Cites Work
- Bipartite permutation graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Algorithms for interval catch digraphs
- Recognizing interval digraphs and interval bigraphs in polynomial time
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- Algorithmic graph theory and perfect graphs
- On the Maximum Uniquely Restricted Matching for Bipartite Graphs
- The LBFS Structure and Recognition of Interval Graphs
- Certifying Algorithms for Recognizing Interval Graphs and Permutation Graphs
- Interval digraphs: An analogue of interval graphs
- Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
- Partially Ordered Sets
- Uniquely restricted matchings
This page was built for publication: Uniquely Restricted Matchings in Interval Graphs
